BZOJ1951: [Sdoi2010]古代猪文

给定整数n,g,求$q^{sum_{k|n} C_n^k }mod 999911659.$

999911659=2 * 3 * 4679 * 35617
欧拉定理，中国剩余定理，Lucas定理杂糅.

代码很友好：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,g,p[4]={2,3,4679,35617},a[4],mod=999911658;
ll ans,jc[36000];
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!a)
	{
		x=0;y=1;
		return;
	}
	exgcd(b%a,a,y,x);
	x-=b/a*y;
}
ll inv(ll a,ll p)//a对p的逆元 
{
	ll x,y;
	exgcd(a,p,x,y);
	x=(x%p+p)%p;
	return x;
}
ll power_mod(ll a,ll b,ll c)
{
	ll ans=1%c;a%=c;
	while(b)
	{
		if(b&1)ans=ans*a%c;
		a=a*a%c;b=b>>1;
	}
	return ans;
}
ll lucas(ll n,ll m,ll k)
{
    if(!m||n==m)return 1;
    else if(n<m)return 0;
    else if(n<k)return jc[n]%k*inv(jc[m]%k,k)%k*inv(jc[n-m]%k,k)%k;
    else return lucas(n/k,m/k,k)*lucas(n%k,m%k,k)%k;
}
void add(int x)
{
	for(int i=0;i<4;i++)a[i]=(a[i]+lucas(n,x,p[i]))%p[i];
}
int main()
{
	scanf("%d%d",&n,&g);
	g%=mod+1;
	if(!g){puts("0");return 0;}
	jc[0]=1;
	for(int i=1;i<35617;i++)jc[i]=jc[i-1]*i%mod;
	for(int i=1;i*i<=n;i++)if(n%i==0)
	{
		add(i);
		if(i*i!=n)add(n/i);
	}
	for(int i=0;i<4;i++)
	{
		ans+=a[i]*(mod/p[i])*inv(mod/p[i],p[i]);
		ans%=mod;
	}
	printf("%lld
",power_mod(g,ans,mod+1));
	return 0;
}