暴力写法：枚举因子，计算有多少个数含有该因子并求和，时间复杂度。

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;
}

优化：上面的代码首先把区间问题转化成区间和区间两个与左端点无关的问题。然后再枚举因子，则因子在区间中出现的次数为。现在我们对上面的代码进行优化。

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

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

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

  • 如果我们可以很快的得到每个块的端点，则我们可以不必一个数一个数的枚举，而是一个块一个块的枚举。这是可以做到的，结论：**如果一个块的右端点为，则左端点为**。这样块的问题就解决了。

  • 虽然块的问题解决了，但是出现了一个新的问题。以区间为例，对于区间里的任意一个数在区间里都有1个数包含因子。但问题是，我们要把因子按最高位分类统计。如果我们要求的因子最高位是2的话，则区间对答案的贡献为0。我们如何统计某个区间里有多少个数的最高位满足要求呢？

  • 同样是先把区间问题转化为区间和区间两个与左端点无关的问题。然后我们枚举数的位数，以最高为7举例。

    • 位数为1，区间为。

    • 位数为2，区间为。

    • 位数为3，区间为。

    • ......

    • 位数为，区间为或。

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

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;
}