数码

https://ac.nowcoder.com/acm/problem/13221 数码传送们
本蒟蒻第一次写题解 希望写得不好的地方苣苣们指出。
首先这道题如果数据小的话直接暴力搞就好 ，但是一看数据1e9暴力的话那么直接就会T死。
讲这题之前 有一个知识点 （不懂得可以去查一下）莫比乌斯反演涉及的一个小知识点，数论分块，恰好这题就使用到了。
可以用到整除分块的形式，大致是这样的：

这个式子，O(n)计算是非常显然的。但，有的时候因为多组数据的要求，可能O(n)并不是正确的时间复杂度。那么这个时候，我们就有一种O( )的做法。这就是：整除分块！
对于每一个n/i我们可以通过打表(或理性的证明)可以发现：有许多n/i的值是一样的，而且它们呈一个块状分布；再通过打表之类的各种方法,我们惊喜的发现对于每一个值相同的块，它的最后一个数就是n/(n/i)。得出这个结论后，我们就可以做的O( )处理了。
举个例子：
n=10;
i=1; 10/1=10;（后面偷懒）
i=2; 5
i=3;3
i=4;2
i=5;2
i=6;1
i=7;1
i=8;1
i=9;1
i=10;1
然后我们可以清晰地看到自从6之后我们就有一个明显的关系：这时候就用上了数论分块； n/(n/i);
当i=6，an=10/(10/6)=10; 是不是我们就可以得到6-10的值是相同的呢。
好啦 回归该题，此题就是找该因子的最高位，那么我们就一次枚举就好，比如K=1，那么就是[1,1],[10,19],[100,199]........,我们可以清晰地看到每次的区间左边都是上一次的10倍，右边是10倍加9，那么我们就可以去利用该关系和数论分块来直接搞。注意的是 每次你的区间右边要和你的输入区间取min因为越界，比如样列是1 8，但是我们选的区间枚举却是1-9，那么是不是越界啦。接下来上代码

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
const int maxx=1e6+100;
int solve(ll r,ll x)
{
    ll ans=r/x; //最高位当前为X，然后能整除的个数，
    ll st=x*10,en=min(r,x*10+9);//这是枚举每个区间[x,x+9],st是左边，en是右边的，注意右边和样列的区间 不要越界
    for(;st<=r;st*=10,en=en*10+9)
    {
        ll k=min(r,en);//和上面第二行一样，注意越界
        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()
{
   fio;
    ll r,l;
    cin>>l>>r;
    for(int i=1;i<=9;i++)
    {
        cout<<solve(r,i)-solve(l-1,i)<<endl;
    }
}

嘿嘿 ，大概就是这样 ，不懂可以自己手动模拟一下1 20//不会的可以私信我