【每日一题】数码
数码
https://ac.nowcoder.com/acm/problem/13221
题目
题目描述： 给定两个整数 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;
}
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
查看6道真题和解析