链接
https://ac.nowcoder.com/acm/problem/13221
题意
给定两个整数 $l$ 和 $r$，对于所有满足 $1 \le l \le x \le r \le 10^9$ 的 $x$ ，记录 $x$ 的所有因数的最高位，求$1\sim 9$ 每个数码出现的次数
思路
我们可以先计算 $1 \sim r$，然后减去 $1 \sim l-1$
因子都是成对出现的，记两个因子为 $a,b(a<b)$ 我们可以枚举 $a(a \le \sqrt{n})$，那么 $a*b$ 在 $1 \sim r$ 的范围内 $b$ 的取值范围为 $[a+1,r/a]$
对于 $b$ 的首位数，我们从低位开始枚举 $1 \sim 9$，设位数为k，首位数为x，则左界是 $\max(a+1,x*10^k)$，右界是 $\min(r/a,(x+1)*10^k-1)$，如果右界 $\ge$ 左界，那么这个区间合法
对于 $a$ 的首位数的个数是 $b$ 的取值范围长度 $+1$，因为 $b>a$ ，而 $a*a$ 也是合法的，需要记录一次
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20;
ll a[N],b[N];
int high(int x) {
while(x/10) x/=10;
if(x==0) return 1;
else return x;
}
void calc(int x,ll *a) {
for(int i=1;i*i<=x;i++) {
int l=i+1,r=x/i;
for(int j=1;j<=r;j*=10)
for(int k=1;k<=9;k++) {
int x=max(j*k,l);
int y=min(j*(k+1)-1,r);
if(y-x>=0) a[k]+=y-x+1;
}
a[high(i)]+=r-i+1;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int l,r;
cin>>l>>r;
calc(r,a);
calc(l-1,b);
for(int i=1;i<=9;i++) cout<<a[i]-b[i]<<endl;
return 0;
}
|