30分TLE代码求调
查看原帖
30分TLE代码求调
941962
Kasa_楼主2023/5/2 10:11
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int Max=1e5+5; 
LL n,m,p,num[Max],pr[Max],len;
inline LL exgcd(LL a,LL b,LL &x,LL &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	LL t=exgcd(b,a%b,y,x);
	y-=a/b*x;

	return t;
}
inline LL inv(LL a,LL b){
	LL x,y;
	exgcd(a,b,x,y);
	x=(x+b)%b;
	return x; 
}
inline LL power(LL a,int b,LL p){
	LL ans=1;
	while(b){
		if(b&1)ans=(ans*a)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return ans;
}
inline void init(LL p){
	LL k=p;
	for(int i=2;i*i<=k;++i){
		if(k%i==0){
			pr[++len]=i;
			num[len]=1;
			while(k%i==0){
				k/=i;
				num[len]*=i;
			}
		}
	}
	if(k>1){
		++len;
		pr[len]=num[len]=k;
	}
}
inline LL fac(LL n,LL p,LL k){
	if(!n)return 1;
	LL ans=1;
	if(n>=k)
		for(LL i=1;i<=k;++i)
			if(i%p)
				ans=ans*i%k;
	ans=power(ans,n/k,k);
	for(int i=1;i<=n%k;++i)
		if(i%p)
			ans=ans*i%k;
	return ans*fac(n/p,p,k)%k; 
}
inline LL C(LL n,LL m,LL p,LL k){
	if(n<m)return 0;
	if(!m||n==m)return 1;
	LL fn=fac(n,p,k);
	LL fm=fac(m,p,k);
	LL fnm=fac(n-m,p,k);
	LL tot=0;
	for(int i=n;i;i/=p)tot+=i/p;
	for(int i=m;i;i/=p)tot-=i/p;
	for(int i=(n-m);i;i/=p)tot-=i/p;
	fnm=inv(fnm,k);
	fm=inv(fm,k);
	return fn*fm%k*fnm%k*power(p,tot,k)%k;
} 
inline LL CRT(LL n,LL m,LL p){
	LL ans=0;
	for(int i=1;i<=len;++i){
		LL M=p/num[i];
		LL invm=inv(M,num[i]);
		LL x=C(n,m,pr[i],num[i]);
		ans=(ans+x*invm%p*M%p)%p;
	}
	return ans;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&p);
	init(p);
	printf("%lld",CRT(n,m,p));
	return 0;
}
2023/5/2 10:11
加载中...