牛客网题库——1数码

问题描述：

       给定两个整数

 和 

，对于所有满足1 ≤

 ≤

 ≤

≤ 10^9 的

，把 

 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。

输入描述：

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

输出描述:

输出9行。

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

示例1

输入

1 4

输出

4
2
1
1
0
0
0
0
0
           

问题转化：

 , 即

 与

之间的所有整数的所有约数的最高数位数码频数 等于 1到

之间的所有整数的此项问题解 与 1到

 -1之间的所有整数的此项问题解  的差 

求解思路：    对于问题

, 考虑采用枚举约数的方式求解，遍历其中所有的整数，对于每一个整数，考量其都可以作为谁的约数，然后计数其被约数的个数，将此个数累加在该数最高位数码频数上

具体求解方法：

1.  对于整数M，其被约数有M， 2M， 3M， ... (不超过n) ，那么被约数个数可以这样求得

2.  在枚举约数时，鉴于问题求的是最高数码频数，拟将所有约数以数量级划分阶段进行处理，不妨设其最高数码p和位数q (依题意得q不大于10)，这样每个阶段的第一个数可以表示为

，最后一个数可以表示为

那么对于数码p，其频数就可以这样计算了

3.  枚举约数时，有一个规律值得我们注意，紧邻的几个数往往具有相同个数的被约数，充分利用这个规律将会大大加快我们的枚举速度。对于数M，其后面跟着几个与其拥有相同个数被约数的整数呢，这个我们要用到数M除n之后的余数rema，看看余数里还够整数M增加几个1，设d = 

，则整数M每增一，余数就减去一个d。照如此算，整数M之后还有

个整数与其拥有相同个数的被约数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll_int;
ll_int l, r;
   
vector<ll_int> solve(ll_int r) {   //设r = 100
    vector<ll_int> ans(10, 0);
    for(ll_int u = 1; u <= 9; ++u) {  //u为最高位数码  设此时u = 3
        for(ll_int v = 1; u * v <= r; v *= 10) {  // u * 10^   ，设此时v = 10
            ll_int s = u * v, e = min(u * v + v - 1, r);    // s = 30 e =min( 39, 100)
            ll_int slip;
            for(ll_int i = s; i <= e; i += slip) {  
                //采用快速求解 此时30 31 32 33的mult是一致的，故可以不必再去遍历31 32 33，
                ll_int mult = r / i, rema = r % i;   //mult = 3， rema = 10
                slip = 1; slip += min(rema / mult, e - i);   
                //一般情况下采用的都是rema / mult ， 当前遍历值每增一，总的就增一个mult，
                //故需要计算余数中还可容纳几个相同商的约数
                ans[u] += mult * slip;
            }
        }
    }
    return ans;
}
   
int main(void) {
    while(~scanf("%lld%lld", &l, &r)) {
        vector<ll_int> ans1 = solve(l - 1);
        vector<ll_int> ans2 = solve(r);
        for(int i = 1; i <= 9; ++i)
            printf("%lld\n", ans2[i] - ans1[i]);
    }
}
           

链接：https://ac.nowcoder.com/acm/problem/13221

来源：牛客网