题目
题目描述: 给定两个整数 l 和 r ,对于所有满足1 ≤ l ≤ x ≤ r ≤ 109 的 x ,把 x 的所有约数全部写下来。
对于每个写下来的数,只保留最高位的那个数码。求1~9每个数码出现的次数。
一行,两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)。
输出9行,第 i 行,输出数码 i 出现的次数。
解析
根据题目意思,这道题就是要求出 l 和 r 之间的每个因子,求最左边数字的数量之和。
所以:
- 我们可以先枚举出几个例子:可以发现以下的规律。(比如我们的左右为 l 和 r )
- l到r之间的每一个因子是什么都不重要,因为我们只要统计因子数量。
- 因子都是成对存在。可以表现为a x b。
- 如果a确定为一个值,在某个区间内,b一定是连续的。
- a出现的次数就是对应b的区间的长度,提取出a的最高位,然后这个最高位出现的次数加上b区间的长度。
我们可以先求出[1,r],再求[1,L-1],最后的答案就是[1,r]-[1,L-1]。
- 相减就是之间的答案了。
打代码:
- 我们就先存好。
- 然后求解出两个区间。
- 输出差值就好。
- 看代码~
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; } } //函数区