题目描述

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

输入描述:

一行，两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)。

输出描述:

输出9行。

第 i 行，输出数码 i 出现的次数。

示例1

输入

1 4

输出

4
2
1
1
0
0
0
0
0

思路：

求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次

其实随着除数的增大，只要不能够被整除，那么跨度是很大的，优化的次数也就更多

经过测试 这样跳块的复杂度总共大概是 sqrt

总复杂度就是9 * 10 * sqrt

AC：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(ll r,ll x){
    ll ans=r/x;///算x能整除的个数 其实这里x就是一个个位数 最高位数字自然为x  
   ///下面的代码都是为了算x作为最高位的数字作为约数的次数
    ll st=x*10,en=min(r,x*10+9);//st为下界 en为上界
    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;
}