链接
https://ac.nowcoder.com/acm/contest/4784/B
题意
求一个最小的正整数 $n$，使得 $n!$ 是 $p$ 的倍数
思路
分解 $p$ 的质因数，然后二分 $1\sim p$，拥有 $p$ 的所有质因数就是 $p$ 的倍数
$n!$ 拥有质因数 $i$ 的个数为：$\lfloor\frac{n}{i}\rfloor+\lfloor\frac{n}{i^2}\rfloor+\lfloor\frac{n}{i^3}\rfloor+…$
代码
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
const int N=100010;
int tot,p[N],cnt[N];
void Divide(int x) {
tot=0;
for(int i=2;i*i<=x;i++) {
if(x%i==0) {
p[++tot]=i;
cnt[tot]=0;
while(x%i==0) {
cnt[tot]++;
x/=i;
}
}
}
if(x>1) p[++tot]=x,cnt[tot]=1;
}
int check(int x) {
for(int i=1;i<=tot;i++) {
int temp=x,t=0;
while(temp) t+=temp/p[i],temp/=p[i];
if(t<cnt[i]) return false;
}
return true;
}
int BinarySearch(int x) {
int l=1,r=x;
while(l<r) {
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
return l;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--) {
int x;
cin>>x;
Divide(x);
cout<<BinarySearch(x)<<endl;;
}
return 0;
}
|