Solution

数论分块，就是利用一段区间内的数整除同一个数结果相同的性质减少运算量的技巧。

回到题目，要求区间 内的答案。已知的是 内数 当做约数的次数为 ，所以问题可以转化为区间 与区间 的答案之差。

暴力计算的话，时间复杂度是 的，不能承受。所以使用数论分块来减少计算量：由于整除向下取整的性质，所以必然存在很多段区间，区间内部整除结果相同，可以合并计算。具体的分块方法：将 作为整个区间。证明过程可以百度。( 好难)

由于本题要求只统计最高位，所以可以将每一位分开处理，方便计算。

时间复杂度： 。

Code

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll Ask(ll u,ll r){
    ll x,y,ans=0;
    for(ll i=1;i<=r/u;i*=10){
        x=u*i,y=min(r,x+i-1);
        for(ll j=x,k;j<=y;j=k+1){
            k=min(y,r/(r/j));
            ans+=(k-j+1)*(r/j);
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    ll l,r;
    cin>>l>>r;
    for(int i=1;i<=9;i++)
        cout<<Ask(i,r)-Ask(i,l-1)<<endl;
    return 0;
}