题目

题目描述:
给定两个整数 l 和 r ,对于所有满足1 ≤ l ≤ x ≤ r ≤ 109 的 x ,把 x 的所有约数全部写下来。
对于每个写下来的数,只保留最高位的那个数码。求1~9每个数码出现的次数。
    
输入描述:
一行,两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)。

输出描述:
输出9行,第 i 行,输出数码 i 出现的次数。


解析

根据题目意思,这道题就是要求出 l 和 r 之间的每个因子,求最左边数字的数量之和

所以:
  1. 我们可以先枚举出几个例子:可以发现以下的规律。(比如我们的左右为 l 和 r )
  2. l到r之间的每一个因子是什么都不重要,因为我们只要统计因子数量。
  3. 因子都是成对存在。可以表现为a x b。
  4. 如果a确定为一个值,在某个区间内,b一定是连续的。
  5. a出现的次数就是对应b的区间的长度,提取出a的最高位,然后这个最高位出现的次数加上b区间的长度。
    我们可以先求出[1,r],再求[1,L-1],最后的答案就是[1,r]-[1,L-1]。
  6. 相减就是之间的答案了。

打代码:
  1. 我们就先存好。
  2. 然后求解出两个区间。
  3. 输出差值就好。
  4. 看代码~


AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);
//代码预处理区

ll l, r;
ll big[10], small[10];
//全局变量区

int get(int x);
void solve(int r, ll a[]);
//函数预定义

int main() {
    js;
    cin >> l >> r;
    solve(r, big);
    solve(l - 1, small);
    for (int i = 1; i <= 9; ++i)
        cout << big[i] - small[i] << endl;
    return 0;
}
int get(int x) {
    while (x / 10) x /= 10;
    return x;
}
void solve(int r, ll a[]) {
    for (int i = 1; i * i <= r; ++i) {
        int t = r / i;
        for (int j = 1; j <= r; j *= 10)
            for (int k = 1; k <= 9; ++k) {
                int x = max(k * j, i + 1);
                int y = min(k * j + j - 1, t);
                if (y >= x)    a[k] += y - x + 1;
            }
        a[get(i)] += t - i + 1;
    }
}
//函数区