记录编号	457054	评测结果	AAAAAAAAAAA
题目名称	[HZOI 2015] 组合数取模	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2017-10-06 16:39:03	内存使用	0.31 MiB

#include<bits/stdc++.h>//费马小定理p必须为素数，欧拉定理还要求欧拉函数，而exgcd只要两数互质即可，在本题更适用 
#define ll long long
using namespace std;
ll n,m,p,ans;
ll gcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;y=0;return a;
	}
	ll t=gcd(b,a%b,x,y);
	ll tem=x;x=y;y=tem-(a/b)*y;return t;
}
ll inv(ll a,ll b){
	ll x,y;gcd(a,b,x,y);if(x<0)x+=b;return x;
}
ll fast(ll x,ll y,ll z){
	ll ans=1;
	while(y){
		if(y&1)ans*=x,ans%=z;
		x=x*x%z;y>>=1;
	}return ans;
}
ll C(ll x,ll pi,ll pk){
	if(!x)return 1;
	ll ans=1,ans2=1;
	for(int i=1;i<=pk;i++)if(i%pi)ans=ans*i%pk;
	for(int i=1;i<=x/pk;i++)ans2=ans2*ans%pk;
	for(int i=1;i<=x%pk;i++)if(i%pi)ans2=ans2*i%pk;//开始忘了加i%pi...还过了除mike新加的以外的点... 
	return ans2*C(x/pi,pi,pk)%pk;//qwq没加取模 
}
ll lucas(ll x,ll y,ll pi,ll pk){//逆元解决不了的啊...pk不一定与c互质 
	ll tem1=C(x,pi,pk);
	ll tem2=C(y,pi,pk);
	ll tem3=C(x-y,pi,pk);
	ll k=0;
	for(int i=x;i;i/=pi)k+=i/pi;
	for(int i=y;i;i/=pi)k-=i/pi;
	for(int i=x-y;i;i/=pi)k-=i/pi;
	return tem1%pk*fast(pi,k,pk)%pk*inv(tem2,pk)%pk*inv(tem3,pk)%pk;
}
int main()
{
	freopen("combinatorial_mod.in","r",stdin);
	freopen("combinatorial_mod.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&p);
	ll tem=p;
	for(int i=2;i*i<=tem;i++){
		if(tem%i)continue;
		ll pk=1;
		while(tem%i==0)pk*=i,tem/=i;
		ans+=inv(p/pk,pk)*(p/pk)%p*lucas(n,m,i,pk)%p;ans%=p;
	}
	if(tem!=1)ans+=inv(p/tem,tem)%p*(p/tem)%p*lucas(n,m,tem,tem);
	cout<<ans%p;
	return 0;
}