0分代码求调
查看原帖
0分代码求调
464318
mr_president楼主2023/5/1 15:57
#include<iostream>
using namespace std;
#define int long long
const int N=1e5+10;
int num[N],pr[N],len;
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	int t=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return t;
}
int inv(int a,int b){
	int x,y;
	exgcd(a,b,x,y);
	x=(x+b)%b;
	return x;
}
int power(int a,int b,int p){
	int ans=0;
	while(b){
		if(b&1){
			ans=(ans+a)%p;
		}
		a=(a+a)%p;
		b>>=1;
	}
	return ans; 
}
void init(int p){
	int 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;
	}
}
int fac(int n,int p,int k){
	if(!n){
		return 1;
	}
	int ans=1;
	if(n>=k){
		for(int 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;
}
int C(int n,int m,int p,int k){
	if(n<m){
		return 0;
	}
	if(!m||n==m){
		return 1;
	}
	int fn=fac(n,p,k);
	int fm=fac(m,p,k);
	int fnm=fac(n-m,p,k);
	int 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(fnm,k);
	return fn*fm%k*fnm%k*power(p,tot,k)%k;

}
int crt(int n,int m,int p){
	int ans=0;
	for(int i=1;i<=len;i++){
		int M=p/num[i];
		int invm=inv(M,num[i]);
		int x=C(n,m,pr[i],num[i]);
		ans=(ans+x*invm%p*M%p)%p;
	}
	return ans;
}
signed main(){
	int n,m,p;
	cin>>n>>m>>p;
	init(p);
	cout<<crt(n,m,p)<<endl;
	return 0;
}
2023/5/1 15:57
加载中...