题目链接：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;
}

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/136/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。