数码

题意:给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。
题解:最先想到的是枚举[L,R]区间内的每一个数,然后求和,即便最快的也要 ,超时
我们发现只用写出最高位出现的次数所以
下来就是来计算每个 对应的区间
比如 那么最后决定答案的是什么?不就是 在范围的倍数的个数如
然后呢就是如果每一个都要计算的话,那么时间复杂度为 ,这样接着超时(弥天大雾)
举个例子 ,在 的符合的倍数的个数都为 个,所以就可以相当于111*9,然后就可以跳过一部分枚举区间
时间复杂度: (大概)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(ll r,ll x){//假设R=100900,x=9
    ll ans=r/x;//9,18,27,36,也就是在1-R中9的倍数有多少,即首位为9,长度为1
    ll st=x*10,en=min(r,x*10+9);//首位为9,长度为2
    for(;st<=r;st*=10,en=en*10+9){//首位为9,长度递增
        ll k=min(en,r);//防止越界
        for(ll i=st;i<=k;){//表示例如长度为3是,9为首位,的符合数有多少,[900,999]
          ll sum=r/i;//第i个数字的倍数有多少,900,1800,2700,3600
          ll mx=min(r/sum,k);//移动左边界,比如901的倍数有111个,那么902也是111个,一直到909都是111个,
            //那么此时我们可以移动左边界,减少运算次数
          ans+=sum*(mx-i+1);//相同的直接,相乘,然后累加,减少运算次数
          i=mx+1;//左边界移动
        }
    }
    return ans;
}
int main(){
    ll l,r;cin>>l>>r;
    for(int i=1;i<=9;i++){
        cout<<solve(r,i)-solve(l-1,i)<<endl;//计算[L,R]=[1,R]-[1,L-1]
    }
    return 0;
}