数码

来源

美团2017年CodeM大赛-资格赛

题意

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

思路

无法下手，之后看了邓老师的题解有了一点思路，自己做还是做不出来。
首先，的范围可以视为 ，之后考虑怎么对 处理，因为其本身比较大，所以不能直接枚举。所以我们直接从因子角度入手，从 枚举第一个因子 ，对于每一个固定的 ，优化地枚举 使得 。如何优化地枚举不会超时呢？本质上就是求 各个数字首位出现的次数。这里使用邓老师给的例子。

L=1，R=317
最高位是1：1，10-19，100-199，共1+10+100个数字；
最高位是2：2，20-29，200-299，共1+10+100个数字
最高位是3：3，30-39，300-317，共1+10+18个数字
最高位是4：4，40-49，共11个数字；
最高位是5：5，50-59，共11个数字；
最高位是6：6，60-69，共11个数字；
这种情况下能取值的范围是

可以看出，我们对于每个 ，只需对每个首位 根据上面的公式分别计算一次。之后要记得加上 本身对答案的贡献。

另一种思路

分块，本质上枚举因子时直接以块为单位跳跃，贡献是以十次方的速度增长的，这样也可以完成这道题。

WA

int只能通过85%的数据。

代码

#include <iostream>
using namespace std;
typedef long long ll;
ll a[10],b[10];

ll l,r;

ll fir(ll x) {
    ll ans;
    while(x) {
        ans = x%10;
        x/=10;
    }
    return ans;
}

void cal(ll r, ll a[]) {
    for(ll i=1;i*i<=r;i++) { //固定i
        for(ll j=1;j<=r;j*=10) { //j是系数
            for(ll k=1;k<=9;k++) { //最高位为k
                ll tl=max(j*k, i+1); //左界
                ll tr=min(j*(k+1)-1, r/i); //右界
                if(tr>=tl) a[k]+=tr-tl+1;
            }
        }
        a[fir(i)]+=r/i-i+1; // 用了多少个a，就是b的右界减去左界
    }
}

int main() {
    scanf("%lld%lld",&l,&r);
    cal(r,a);
    cal(l-1,b);
    for(ll i=1;i<=9;i++) printf("%lld\n",a[i]-b[i]);
}