每日一题 数码

链接戳这
题意：
求 l<=x<=r 中 x的所有约数的最高位出现的次数
思路：
一开始以为是通过枚举因子反着枚举，看了题解才发现是暴力枚举每个最高数位，然后枚举范围通过整除分块来做，复杂度是 然后呢，枚举最高位，整除分块的思想就马上体现了，由于是求l～r中的，那么数位dp中的思想就马上体现出来了，l～r就是等价于solve(r)-solve(l-1),如何写solve呢，solve函数的含义就是1～x中能被最高位i整除的最高位出现的个数，显而易见一个因数p能把1～x中数整除的个数是 ,那么n/p这个值会出现在一段l～r的区间，这个右区间就是 我们慢慢得跳即可。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int cnt[10];
int l,r;
int L(int x)
{
    int res=0;
    while(x)
    {
        x/=10;
        res++;
    }
    return res;
}
int maxp(int x)
{
    while(x)
    {
        if(x<10)
            return x;
        x/=10;
    }
    return -1;
}
int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int solve(int x,int v)//1～x满足条件的   1~1 10~19 100~199
{
    int res=0;
    for(int i=1;i<=x;i*=10)
    {
        int l=v*i;
        int r=min((v+1)*i-1,x);
        //cout<<l<<" "<<r<<endl;
        for(int j=l;j<=r;)
        {
            int xx=min(x/(x/j),r);
            //cout<<xx<<endl;
            res+=(xx-j+1)*(x/j);
            j=xx+1;
        }
    }
    return res;
}
signed main()
{
    cin >> l >> r;
    for(int i=1;i<=9;i++)
    cout<<solve(r,i)-solve(l-1,i)<<endl;

    return 0;
}