ABC-280解题报告

D. Factorial and Multiple

题意:给你一个 kk,求最小的 nn 使得 kn!k|n!k1012k\le 10^{12}

做法一

考虑将 kk 分解质因数,对于每项 prp^r,都要求 n!n! 中含有至少 rrpp。由于 n!n! 的质因数单调增加,所以可以二分。对于检查某个 nn 是否满足条件,只需要看 nn 以内有多少个 pp 的倍数 + nn 以内有多少个 p2p^2 的倍数……以此类推。对于每个 prp^r 取对 nn 限制最大的那个即可,最后可能剩下的一个 >n>\sqrt{n} 的质因数特判一下。时间复杂度 n+log3(n)\sqrt{n}+\log^3(n)

检查 n!n!pp 的次数使用的方法被称为“勒让德定理(Legendre’s Formula)”,描述是: n!n!pp 的次数等于 k1npk\sum\limits_{k\ge 1} \left\lfloor\frac{n}{p^k}\right\rfloor。证明:首先对于所有的 pp 的倍数都要计算一次贡献,为 np\left\lfloor\frac{n}{p}\right\rfloor;然后对于所有 p2p^2 的倍数,我们希望计算两次贡献,而当前只计算了一次,所以需要再加上 np2\left\lfloor\frac{n}{p^2}\right\rfloor 的贡献。以此类推得到上述结论。

勒让德定理有一个扩展形式,描述为:n!n!pp 的次数等于,nn 减去“将 nn 转化为 pp 进制后的各位之和”,再除以 p1p-1。证明:容易发现 np\left\lfloor\frac{n}{p}\right\rfloor 即为 nnpp 进制下右移一位的结果,np2\left\lfloor\frac{n}{p^2}\right\rfloor 即为 nnpp 进制下右移两位的结果,以此类推。故对于 nn 的第 ii 位(从低到高),它会分别在第 i1,i2,i3,,0i-1,i-2,i-3,\cdots,0 位统计贡献,故第 iieie_i 造成的贡献为 j<ieipj=eipi1p1\sum\limits_{j<i} e_i\cdot p^j=e_i\cdot \frac{p^i-1}{p-1},而总贡献即为每一位的贡献之和(xx 为位数):

i=1xeipii=1xeip1=(ne0)(i=0xeie0)p1=ni=0xeip1\frac{\sum\limits_{i=1}^{x}e_ip^i-\sum\limits_{i=1}^{x}e_i}{p-1}=\frac{(n-e_0)-(\sum\limits_{i=0}^x e_i-e_0)}{p-1}=\frac{n-\sum\limits_{i=0}^x e_i}{p-1}

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int k,ans=0;
cin>>k;
for(int i=2;i*i<=k;i++) {
if(k%i!=0) continue;
int cnt=0,l=1,r=k;
while(k%i==0) cnt++,k/=i;
while(l<r) {
int mid=(l+r)/2,now=0;
for(int x=i;x<=mid;x*=i) {
now+=mid/x;
if(now>=cnt) break;
}
if(now>=cnt) r=mid;
else l=mid+1;
}
ans=max(ans,l);
}
if(k!=1) ans=max(ans,k);
cout<<ans<<endl;
return 0;
}

这个做法有许多本质相同的变种,如:每次将 mid/=xmid\text{/=}x 而不是 x*=ix\text{*=}i;在外部二分,内部整体 check;check 时每步跳跃 ii 地枚举阶乘等。

每次减小 midmid By potato167

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
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t=1;
//cin>>t;
rep(i,0,t) solve();
}

void solve(){
ll K;
cin>>K;
ll ans=0;
auto p=Prime_factorization(K);
for(auto x:p){
ll l=1,r=K;
while(r-l>1){
ll med=(r+l)/2;
ll D=med;
ll tmp=0;
while(med){
med/=x.first;
tmp+=med;
}
if(tmp<x.second) l=D;
else r=D;
}
chmax(ans,r);
}
cout<<ans<<"\n";
}

外部二分,整体 check By IH19980412

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
void solve(){
int k;cin>>k;
auto p = pollard_rho_fast::factorize2(k);
int lb=0, ub = 1e12+5;
while(ub-lb>1){
int mid=(lb+ub)/2;
for(auto x:p){
int num=x.a;
int cnt=x.b;
int t=0;
int now=mid;
while(now){
t += now / num;
now /= num;
}
if(t < cnt) goto fail;
}
ub=mid;continue;
fail:;lb=mid;
}
o(ub);
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
int t; t = 1; //cin >> t;
while(t--) solve();
}

每步跳跃枚举阶乘 By ygussany

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
#include <stdio.h>

void chmax(long long* a, long long b)
{
if (*a < b) *a = b;
}

int main()
{
long long K;
scanf("%lld", &K);

int j;
long long i, ans = 1, tmp, tmpp;
for (i = 2; i * i <= K; i++) {
if (K % i != 0) continue;
for (j = 0; K % i == 0; j++, K /= i);
for (tmp = i; 1; tmp += i) {
for (tmpp = tmp / i, j--; tmpp % i == 0; tmpp /= i, j--);
if (j <= 0) break;
}
chmax(&ans, tmp);
}
if (K >= 2) chmax(&ans, K);
printf("%lld\n", ans);
fflush(stdout);
return 0;
}

提前跑一层最后再加回来 By daisybunny

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
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
map<long long,long long> mp;
long long k;
vector<long long> v;
long long ma;
void fjzys(long long a)
{
long long x=a;
for(long long t=2;t*t<=a;t++)
{
//cout<<t*t<<endl;
if(x%t==0)
v.push_back(t);
while(x%t==0)
{
mp[t]++;
x/=t;
//cout<<t<<" ";
}
}
if(x!=1)
{
v.push_back(x);
mp[x]++;
}
}
int main()
{
cin>>k;
fjzys(k);
for(long long t=0;t<v.size();t++)
{
long long sum=0;
for(long long i=1;;i++)
{
long long x=i;
long long b=0;
while(x%v[t]==0)
{
x/=v[t];
b++;
}
sum+=b+1;//提前跑了一层
if(sum>=mp[v[t]])
{
ma=max(i*v[t],ma);//补回来
break;
}
}
}
cout<<ma;
return 0;
}

做法二

考虑直接枚举 nn,维护当前 n!n!kk 的模数,直到第一次为 00 时满足条件。这个做法直接写肯定会超时,但注意到当 nn 比较大时就将大部分情况覆盖地非常全了,唯一一种没有覆盖到的情况只能是 kk 有一个非常大的质因子。此时该质因子只能出现一次(因为 >k>\sqrt{k}),所以答案的 n=n= 该质因子。

正确性证明:

假设 kkk\sqrt{k} 以内的某个质因子 prp^r,则在枚举 nn 时至少会在每个 pp 的倍数被覆盖一次,所以 nn 保证正确性的枚举上界为最大的 prpr。有 r=logp(k)r=\log_p(k),所以枚举上界为 plogp(k)p\log_p(k),其在 p>2p>2 时单调递增,所以最坏情况有 {p=2,r=log2(k)p=k,r=2\begin{cases}p=2,r=\log_2(k)\\p=\sqrt{k},r=2\end{cases},所以枚举到 2k2\sqrt{k} 即可保证正确性。

另一种证法:在 10410610^4\sim 10^6 内的质因数最多出现两个,所以到 2×1062\times 10^6 即可保证正确性;在 10410^4 以内的质因数最多也只能有不超过 100100 个,所以到 10610^6 就能保证正确性

By noimi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() {
LL(k);
auto f = factor(k);
ll ma = 0;
rep(i, si(f)) { chmax(ma, f[i].fi); }

ll now = 1;
rep(i, 1, ten(8)) {
now = now * i % k;
if(!now) {
OUT(i);
exit(0);
}
}
OUT(ma);
}

还有一种不同的实现,每次枚举到一个数时将它能覆盖到的 kk 的质因数覆盖掉,即将 k/=gcd(i,k)k\text{/=}\gcd(i,k)。当积累的覆盖足够多,直到能将 kk 的所有质因数全部覆盖完,就达到了 i!i!kk 的倍数的目标。

By physharp

1
2
3
4
5
6
k=int(input())
import math
for n in range(1,2000001):
k//=math.gcd(k,n)
if k<2: exit(print(n))
print(k)