数码

https://ac.nowcoder.com/acm/problem/13221
emm，数据范围1e9，顶多O（n）复杂度，但是看题可想而知，复杂度要小于O（n），跟数学有关系；再者，i|n形式，可以考虑考虑数论分块；

#include<iostream>
#include<algorithm>
using namespace std;
  long long l,r;
long long calculate(long long x,long long k)
{
    long long h=0,ans=x/k;//k为第几个数码，ans初始化，对于1~r中，含有k的数的个数为x/k
    long long be=k*10,end=min(x,k*10+9);//枚举，例如：10~19
    for(;be<=x;be*=10,end=end*10+9)//在1~r中含有多少个，10~19,100~199,1000~1999...类似（不超范围）
    {
        h=min(x,end);
        for(int i=be;i<=h;)
        {
            long long tag=x/i;
            long long lim=min(x/tag,h);//数论分块的结论，x/(x/i)，在这个区间里，贡献都一样，为tag
            ans+=tag*(lim-i+1);//lim为右端点-1（即lim+1这个数的贡献与前一个数不一样）
            i=lim+1;
        }
    }
    return ans;
}
int main()
{
    cin>>l>>r;
   for(int i=1;i<=9;i++)
   {
       cout<<calculate(r,i)-calculate(l-1,i)<<endl;
   }
    return 0;
}