题目链接https://ac.nowcoder.com/acm/problem/13221

题面
题面

暴力写法:枚举因子,计算有多少个数含有该因子并求和,时间复杂度$O(n)$。

int gethead(int x) {
    while(x >= 10) x /= 10;
    return x;
}
LL solve(int r, int  x) {
    LL ret;
    for(int i = 1; i <= r; i++) {
        if(gethead(i) != x) continue;
        ret += r / i;
    }
    return ret;
}
int main() {
    int l, r;
    scanf("%d%d", &l, &r);
    for(int i = 1; i < 10; i++) {
        printf("%lld\n", solve(r, i) - solve(l - 1, i));
    }
    return 0;
}

优化:上面的代码首先把区间$[l,r]$问题转化成区间$[1,r]$和区间$[1,l]$两个与左端点无关的问题。然后再枚举因子$i$,则因子$i$在区间$[1,r]$中出现的次数为$r/i$。现在我们对上面的代码进行优化。

  • 直接枚举因子慢是因为每次$i$只能加1。我们可以注意到根据整除分块的性质,$r/i$的值是连续单调递减的块,以10为例如下所示:

| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| r/i | 10 | 5 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |

上面的表格说明在区间$[1,10]$里有10个数包含因子1,5个数包含因子2,3个数包含因子3,以此类推。请注意,从这里开始我们已经不再关心具体是哪些数包含该因子,而只关心包含该因子的数的个数

  • 如果我们可以很快的得到每个块的端点,则我们可以不必一个数一个数的枚举,而是一个块一个块的枚举。这是可以做到的,结论:如果一个块的右端点为$i$,则左端点为$r/(r/i)$。这样块的问题就解决了。
  • 虽然块的问题解决了,但是出现了一个新的问题。以区间$[6,10]$为例,对于区间$[6,10]$里的任意一个数$x$在区间$[1,10]$里都有1个数包含因子$x$。但问题是,我们要把因子按最高位分类统计。如果我们要求的因子最高位是2的话,则区间$[6,10]$对答案的贡献为0。我们如何统计某个区间$[l,r]$里有多少个数的最高位满足要求呢?
  • 同样是先把区间$[l,r]$问题转化为区间$[1,r]$和区间$[1,l]$两个与左端点无关的问题。然后我们枚举数的位数$n$,以最高为7举例。

    • 位数为1,区间为$[7,7]$。
    • 位数为2,区间为$[70,79]$。
    • 位数为3,区间为$[700,799]$。
    • ......
    • 位数为$n$,区间为$[7*10^{n-1},8*10^{n-1}-1]$或$[7*10^{n-1},r]$。

通过枚举数的位数,我们可以$O(1)$的计算出每一个不同的位数对答案的贡献,只需要注意不要超过右端点$r$即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

LL getnum(LL r, LL x) {//返回区间[1,r]中有多少个数最高位为x
    LL ret = 0;
    for(int i = 1; x * i <= r; i *= 10) {
        ret += min((x + 1) * i - 1, r) - x * i + 1;
    }
    return ret;
}
LL solve(LL maxnum, LL x) {
    LL ret = 0, cnt;
    for(int l = 1, r; l <= maxnum; l = r + 1) {
        cnt = maxnum / l;
        r = maxnum / cnt;
        ret += cnt * (getnum(r, x) - getnum(l - 1, x));
    }
    return ret;
}
int main() {
    int l, r;
    scanf("%d%d", &l, &r);
    for(int i = 1; i < 10; i++) {
        printf("%lld\n", solve(r, i) - solve(l - 1, i));
    }
    return 0;
}
Last modification:April 16th, 2020 at 09:35 pm
如果觉得我的文章对你有用,请随意赞赏