数码

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

思路：
求l到r的个数 转换为求1到r的个数 减去 1到l-1的个数
可以看到 l和r的长度长达1e9 如果暴力算每个的话 光是枚举x就要1e9
可能会想到枚举约数，但是这样也还不够，复杂度还是高的批爆
枚举约数是肯定没错的，问题是考虑如何去优化
可以考虑去枚举以x为最高位的 区间的约数的个数
比如求最高数码x=1 枚举的区间的约数就是 [1,2) [10,20） [100,200） [1000,2000)…
这样有个好处 就是最高位的数都是一样的 就不需要特意去计算了
这样就够了吗？远远不够 就拿[1e8,2e8）这个区间来说 跑完这个 1s估计也用完了

其实到这里这题也快结束了，还差最后一个优化点，也就是最重要的一点 下面的内容都是为了说这个优化点 也就是除法分块
对于一个数a来说，a除以一个数b的值如果要想少一，其中除数b需要成倍成倍的往上增加
看不太明白？ 没关系请继续往下看

下面举个例子来说 比如r=83 我们要求最高位为1的约数的个数 这里模拟一下过程

首先r/1=83 因为每个数都是1的倍数 这是第一个区间[1,2)
接下来第二个区间 [10,20) 我们计算 a/10=83/10=8，意思是83内有8个数是10的倍数
接下来注意了 我们计算83/8=10，这里计算的是乘8后≤r的最大值是多少
也就是对于83而言 83除以[10,10]这个区间的任意一个数的值都为8
这里可能还看不出什么来 继续往下
a/11=83/11=7 83/7=11 同理 83除以[11,11]这个区间的任意一个数的值都为7
a/12=83/12=6 83/6=13 同理 83除以[12,13]这个区间的任意一个数的值都为6
那么我就不需要在计算13的情况了 因为对于12到13 整除83后都等于 6 也就是说
83内是12的倍数有6个 是13的倍数也有6个 那么最高位是1的频数就是 6 * (13-12+1)=12
**a/14=83/14=5 83/5=16 这样的话区间就是 [14,16]了 下一个除数就跑到了17 **
a/17=83/17=4 83/4=21 区间就是[17,21]，这里注意一下 右边界已经超过了19了 所以右边界要注意比较 那么到这里区间[10,20）的过程就模拟完了
上面仅仅是为了模拟一下过程 如果没有get到优化点请继续看下面的粗体部分

如果暴力进行的话[10,20）需要进行10次 而上述过程只用了4次
区间太小可能看不出来什么优化
比如 如果这个a是3e8 我们计算[1e8,2e8）这个区间
3e8/1e8=3 3e8/3=1e8 区间就是只有1e8自己一个值
3e8/(1e8+1)=2 3e8/2=1.5e8 这个区间[1e8+8,1.5e8]跨度整整达到了5e7之大
接下来3e8/(1.5e8+1)=1 3e8/1=3e8 此时区间更大了[1.5e8+1,3e8] 当然了 3e8>=2e8
所以区间应该是[1.5e8+1,2e8） 优化点有多大？暴力这个区间 高达1e8次 这个优化到了只需要3次

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(ll r,ll x){
    ll ans=r/x;
    ll st=x*10,en=min(r,x*10+9);
    for(;st<=r;st*=10,en=en*10+9){
        ll k=min(en,r);
        for(ll i=st;i<=k;){
          ll sum=r/i;
          ll mx=min(r/sum,k);
          ans+=sum*(mx-i+1);
          i=mx+1;
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    ll l,r;cin>>l>>r;
    for(int i=1;i<=9;i++){
        cout<<solve(r,i)-solve(l-1,i)<<endl;
    }
    return 0;
}