题目描述

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

思路

我们设定一个函数calc(x)可以计算1-x中1-9每个数码出现的次数，那么我们只需计算两次，分别是calc(r)和calc(l-1)然后相减就行
那么我们如何计算设计calc函数呢？
那么我们要计算最高位为1-9肯定是要循环1-9，我这里就举例如何计算最高位为1的，其他位类似。
我们先预处理一个数组存每一位的最小非0数
即1位数最小是1, 2位数最小是10……
下面对于不同的位数我们有两个思路，现在我们以2位数为例
方法1：
2位数1开头的分别是10-19，那么我们枚举10-19，for(int i=10;i<=19;i++)
那么x/i就是1-x中含有i的因数的数的个数，这个很好理解
方法2：
我们让x去除以2位数开头最小的数，我们假设他为_ed，然后我们循环1-_ed,for(int i=1;i<=_ed;i++),现在我们和上面的思路不一样，我们求10-19中每一个数乘以i的数在x范围内的个数。

我们会发现方法1在位数较少时效率较高，方法2在位数较多时效率较高，他们是互补的，那么我们就运用分块的思想，当位数少时用方法一，位数多时用方法二。
复杂度
#代码

//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
vector<ll> v;
ll *ans;
ll *ans2;
ll l,r;

void pre()
{
    ll tmp=1;
    for(int i=0;i<10;i++)
    {
        v.push_back(tmp);
        tmp*=10;
    }
}

ll* calc(ll x)
{
    ll *ans=new ll[10];
    for(int i=0;i<10;i++)
        ans[i]=0; 
    for(int num=1;num<=9;num++)
    {
        //枚举位数
        for(auto i:v)
        {
            if(i<=100000)
            {
                //方法一
                ll st=i*num;
                ll ed=st+i-1;
                if(st>x)
                    break;
                for(ll j=st;j<=ed;j++)
                {
                    ans[num]+=x/j;
                }
            }
            else
            {
                //方法二
                ll st=i*num;
                ll ed=st+i-1;
                if(st>x)
                    break;
                ll _ed=x/st;
                for(int j=1;j<=_ed;j++)
                {
                    ll a=x-st*j;
                    ans[num]+=min(a/j+1,ed-st+1);
                }
            }
        }    
    }
    return ans;    
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>l>>r;
    pre();
    ans2=calc(r);
    ans=calc(l-1);
    for(int i=1;i<=9;i++)
        cout<<ans2[i]-ans[i]<<endl;    
     return 0;
}