本题对我这种蒟蒻来说还是太难了啊。。。
首先想到的其实是分块打表，但是1e9的数据我连暴力都跑不出。

题意：

给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。

思路：
分块打表是之前听来的，也没写过。于是想着在这题上试试。既然要打表，首先想着写个暴力呗。
如果按照题意去暴力的话，那么需要枚举x，然后对每个x再枚举约数，这样复杂度是O（n*sqrt(n)），暴力也跑不动了。
那么改成枚举约数i，显然对于[l,r]区间，可以得到r/i-(l-1)/i个数满足条件的。换言之，可以得到r/i-(l-1)/i个约数i，那么我只要枚举i从[1,r]就好了。

for(int i=1;i<=r;i++){
    ans[get(i)]+=r/i-(l-1)/i      //这里的get(i)表示求i的最高位
}

这样复杂度是O(n)，还是太暴力了。
仔细想一想，这里的约数i没有必要枚举到r。其实最小枚举到sqrt(r)就好了。但是这样的话，我们就要考虑剩下的没有枚举到的情况了。显然后面没有枚举到的情况，都包含在前面的x=a*b的b中，因为保证了a<=sqrt(r)，我们可以计算出满足条件的b>=sqrt(r)的个数为r/a-(l-1)/a个。为了方便，我们可以把[l,r]的问题分解成[1,r]-[1,l-1],那么上面的个数我们可以简化为r/a个。
事实上，我们是可以得到这r/a个数分别是哪些数的，他们其实是[1,r/a]中的数（而且是连续的！）

好了，接下来就是如何快速计算[1,r/a]中的数的最高位情况了。
由于我们只要求最高位的情况，所以我们考虑枚举最高位x的时候的在[1,r/a]中有多少个数满足。（我觉得这种思考方式正是我所需要的，有时候真的要敢想。）这里题解里放了一个例子，很直白很容易看懂：
假设r=317,

最高位是1：1，10-19，100-199，共1+10+100个数字；
最高位是2：2，20-29，200-299，共1+10+100个数字
最高位是3：3，30-39，300-317，共1+10+18个数字
最高位是4：4，40-49，共11个数字；
最高位是5：5，50-59，共11个数字；
最高位是6：6，60-69，共11个数字

可以找到规律的，方法就是枚举位数num，然后枚举最高位k，显然我们可以快速得到答案为ans=k * 10^(num-1),min(r,(k+1) * 10^(num-1)-1)。

好了，最终的答案我们可以知道了，枚举第一个约数a,然后可以得到第二个约数b的取值范围为[1,r/a]。这里为了防止重复，其实b的取值范围是[a,r/a]。然后我们通过上面的方法枚举出[a,r/a]中的情况，这里不要忘记约数a出现的次数r/a-a也要加上去。

代码：

#include<bits/stdc++.h>
using namespace std;
long long ans[10];
int get(int x){
    while(x>=10)x/=10;
    return x;
}
int min(int a,int b){
    return a<b?a:b;
}
void work(int x,int d){
    int num=0;
    int tmp=x;
    while(tmp){
        num++;
        tmp/=10;
    }
    for(int i=num;i>=1;i--){       //枚举位数
        for(int k=1;k<=9;k++){      //枚举最高位
            int l,r;
            l=k*pow(10,i-1);
            r=min(x,(k+1)*pow(10,i-1)-1);
            if(l>r)ans[k]+=0;
            else ans[k]+=d*(r-l+1);
        }
    }
}
void solve(int r,int d){
    for(int a=1;a<=sqrt(r);a++){
        int lb=a,rb=r/a;
        int num=0;
        work(rb,d);
        work(lb-1,-d);
        ans[get(a)]+=d*(rb-lb);    //第一个约数a的情况也加上去
    }
}
int main()
{
    int l,r;
    cin>>l>>r;
    solve(r,1);
    solve(l-1,-1);
   // for(int i=1;i<=r;i++)ans[get(i)]+=r/i-(l-1)/i;
    for(int i=1;i<=9;i++)cout<<ans[i]<<endl;
    return 0;
}

画一条分割线，本题我用分块打表试了一下，但是1e9复杂度太高了（其实是因为太弱），所以我打了个1e6的表。
首先我把r个数分块成block=sqrt(r)+1个块（这个+1看r是不是完全平方数）
然后打表，每一个块的长度就是r/block，暴力打表在每一个块里计算出各个位数的次数。
接着询问[l,r]的时候，我们可以先计算出l和r所在的块，然后把中间的几个块直接加起来，l和r所在的块去暴力计算。这样子的复杂度就是O(sqrt(r)）级别的。
打表：

#include<bits/stdc++.h>
using namespace std;
const int M=1000000;
int block;
long long bl[1040][10];
int get(int x){
    while(x>=10)x=x/10;
    return x;
}
int main()
{
//    freopen("oooo.out","w",stdout);
    int len;
    block=sqrt(M);
    if(sqrt(M)*sqrt(M)!=M)block++;
    len=M/block;
    for(int i=0;i<block;i++){
        int r=(i+1)*len;
        int l=i*len+1;
        for(int j=1;j<=r;j++){
            bl[i][get(j)]=bl[i][get(j)]+1ll*(r/j-(l-1)/j);
        }
    }
    for(int i=0;i<block;i++){
        for(int j=1;j<=9;j++)cout<<bl[i][j]<<',';
        cout<<endl;
    }
    return 0;
}

分块计算：

#include<bits/stdc++.h>
using namespace std;
long long bl[1004][9]={2363,1262,855,671,480,416,371,339,312,
3414,1323,924,676,585,489,378,343,317,
2917,2325,903,705,582,458,428,344,316,
3247,1316,1922,693,557,485,427,344,318,
3000,1825,907,1702,570,482,392,376,317,
3198,1818,916,695,1574,466,413,369,316,
3029,1655,1413,699,560,1489,407,361,317,
3175,1652,1414,700,565,470,1425,358,317,
3051,1907,914,1201,572,476,400,1372,318,
//...表太长，省略了 
};
int get(int x){
    while(x>=10)x/=10;
    return x;
}
const int M=1000000;
int main(){
    int len,block;
    block=sqrt(M);
    if(sqrt(M)*sqrt(M)!=M)block++;
    len=M/block;
    int l,r;
    long long ans[10];
    memset(ans,0,sizeof(ans));
    cin>>l>>r;
    int b1,b2;
    b1=(l-1)/block+1;b2=(r-1)/block-1;
    for(int i=b1;i<=b2;i++){         //跨块计算
        for(int j=0;j<9;j++){
            ans[j+1]+=bl[i][j];
        }
    }
    if((l-1)/block==(r-1)/block){        //同一块内
        for(int i=l;i<=r;i++){

            for(int j=1;j<=sqrt(i);j++){
                if(i%j==0){
                    int tmp=get(j);
                    ans[tmp]+=1;
                    tmp=get(i/j);
                    ans[tmp]+=1;
                    if(i/j==j)ans[tmp]-=1;
                }
            }
        }
    }
    else {            //边缘分开暴力计算
        for(int i=l;i<=b1*len;i++){
            for(int j=1;j<=sqrt(i);j++){
                if(i%j==0){
                    int tmp=get(j);
                    ans[tmp]+=1;
                    tmp=get(i/j);
                    ans[tmp]+=1;
                    if(i/j==j)ans[tmp]-=1;
                }
            }
        }
        for(int i=(b2+1)*len+1;i<=r;i++){

            for(int j=1;j<=sqrt(i);j++){
                if(i%j==0){
                    int tmp=get(j);
                    ans[tmp]+=1;
                    tmp=get(i/j);
                    ans[tmp]+=1;
                    if(i/j==j)ans[tmp]-=1;
                }
            }
        }
    }
    for(int i=1;i<=9;i++)cout<<ans[i]<<endl;
}