专栏文章

题解：CF2153E Zero Trailing Factorial

MMaxBlazeResFire
CF2153E题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minm4jq1
此快照首次捕获于
2025/12/02 04:39
3 个月前
此快照最后确认于
2025/12/02 04:39
3 个月前
查看原文
Observation1\rm Observation1：vk(x!)v_k(x!) 就是 [1,2,⋯ ,x][1,2,\cdots,x] 中含有的 kk 的个数之和。
我们现在需要选择一个 kk，使得 [1,x][1,x] 含有的 kk 的个数严格小于 [1,n][1,n] 含有的 kk 的个数。换句话说，我们需要选择一个 k≤mk\leq m 满足 k∣n!x!\displaystyle k\mid\frac{n!}{x!}，且 [1,x][1,x] 中含有的 kk 需要尽可能少。
用构造题的思路，我们想一些简单情况。不难发现：如果 (x,n](x,n] 中有一个质数，那么直接取这个质数，可以直接获得 00 的贡献，非常优。
然后我们打一个表。发现 [1,107][1,10^7] 内相邻的两个质数的最大差距不超过 154154。所以我们找到 ≤n\leq n 的最大质数 pp，直接取 k=pk=p 即可。我们就只需要额外处理 x∈[p,n)x\in[p,n) 的情况，其中 xx 的取值个数不超过 k0=154k_0=154。
Observation2\rm Observation2：kk 取一个质数的若干次幂必然不劣（根据出题人给的提示可以发现，若一个合数可以区分开 a,ba,b，一定可以用这个合数的某个质因子的若干次幂区分开它们）。
然后我们再毛估估一下 [p,n)[p,n) 内所有数分解后本质不同质数的个数，发现也就不超过 k1=30k_1=30 个。
考虑一个质数 pp 的贡献。记 [1,n][1,n] 中有 p[1,n]p[1,n] 个 pp，[1,x][1,x] 中有 p[1,x]p[1,x] 个 pp，那么我们需要找到一个最大的 ee，满足 pe≤mp^e\leq m，且 ⌊p[1,x]e⌋<⌊p[1,n]e⌋\displaystyle\lfloor\frac{p[1,x]}{e}\rfloor<\lfloor\frac{p[1,n]}{e}\rfloor。注意到由于 pe≤mp^e\leq m 的存在，我们可以直接倒序枚举 O(log⁡n)O(\log n) 个 ee，然后 O(log⁡n)O(\log n) 计算 p[1,x],p[1,n]p[1,x],p[1,n] 比较，然后就可以求得 w(x,n)w(x,n)。我们一共需要对 k0k_0 个数计算 k1k_1 个质数的贡献，每个质数造成复杂度 O(log⁡2n)O(\log^2n)。总计下来，复杂度 O(tk0k1log⁡2n)O(tk_0k_1\log^2n)。取 t,k0t,k_0 同阶，k1,log⁡nk_1,\log n 同阶，不超过 10810^8，可以通过，而且 ee 不用枚举到底，运行次数远小于上界。可以很轻松地通过。
CodeCPP
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 10000005

int notp[MAXN],prime[MAXN],minp[MAXN],ptot = 0;

inline void Euler(){
	notp[1] = 1;
	for( int i = 2 ; i < MAXN ; i ++ ){
		if( !notp[i] ) prime[++ptot] = i;
		for( int j = 1 ; j <= ptot && i * prime[j] < MAXN ; j ++ ){
			notp[i * prime[j]] = 1,minp[i * prime[j]] = prime[j];
			if( i % prime[j] == 0 ) break;
		}
	}
}

int n,m,Min[MAXN];

set<int> S;

inline void Get_Cprs( int x ){
	while( x > 1 ){
		if( notp[x] ){
			int p = minp[x];
			S.insert( p );
			while( x % p == 0 ) x /= p;
		}
		else{ S.insert( x ); return; }
	}
}

inline int calc( int x , int p ){
	int res = 0;
	while( x ){ res += x / p,x /= p; }
	return res;
}

inline void solve(){
	scanf("%lld%lld",&n,&m);
	int p = n; while( notp[p] ) p --;
	for( int x = p ; x <= n ; x ++ ) Get_Cprs( x );
	for( int x = p ; x < n ; x ++ ) Min[x] = (int)1e8;
	int Ans = 0;
	for( int ele : S ){
		int maxe = 0,tmp = 1; while( tmp * ele <= m ) tmp *= ele,maxe ++;
		for( int x = n - 1 ; x >= p ; x -- ){
			int hasx = calc( x , ele ),hasn = calc( n , ele );
			for( int e = maxe ; e ; e -- )
				if( hasx / e < hasn / e ) Min[x] = min( Min[x] , hasx / e );
		}
	}
	for( int x = p ; x < n ; x ++ ) Ans += Min[x];
	printf("%lld\n",Ans);
	S.clear();
}

signed main(){
	Euler();
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...