【BZOJ1951】[Sdoi2010]古代猪文
Description
求$X=\sum\limits_{d|n}C_n^d$，$Ans=G^X (\mod 999911659)$。
Input
有且仅有一行：两个数N、G，用一个空格分开。
Output
有且仅有一行：一个数，表示答案除以999911659的余数。
Sample Input
4 2
Sample Output
2048
HINT
10%的数据中，1 <= N <= 50；
20%的数据中，1 <= N <= 1000；
40%的数据中，1 <= N <= 100000；
100%的数据中，1 <= G <= 1000000000，1 <= N <= 1000000000。
题解：由于n很小，可以暴力枚举约数并用Lucas定理计算$C_n^d$的值。但是最后求的是$G^X%P$，所以X要对P-1取模，然而P-1不是质数，所以先分解质因数然后用CRT合并即可。
注意：G=P时费马小定理不成立。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,G,P,ans;
ll v[100000],jc[100000],jcc[100000],ine[100000],A[10];
ll lucas(ll a,ll b)
{
if(a<b) return 0;
if(!b) return 1;
if(a<P) return jc[a]*jcc[a-b]%P*jcc[b]%P;
return lucas(a%P,b%P)*lucas(a/P,b/P)%P;
}
ll calc()
{
ll ret=0;
jc[0]=jcc[0]=ine[0]=jc[1]=jcc[1]=ine[1]=1;
int i;
for(i=2;i<P;i++) jc[i]=jc[i-1]*i%P,ine[i]=P-(P/i)*ine[P%i]%P,jcc[i]=jcc[i-1]*ine[i]%P;
for(i=1;i<=m;i++) ret=(ret+lucas(n,v[i]))%P;
return ret;
}
inline ll pm(ll x,ll y,ll mod)
{
ll z=1;
while(y)
{
if(y&1) z=z*x%mod;
x=x*x%mod,y>>=1;
}
return z;
}
inline ll work(ll a,ll b,ll c)
{
return (c*pm(a,b-2,b)%b+b)%b;
}
int main()
{
scanf("%lld%lld",&n,&G);
if(G==999911659)
{
printf("0");
return 0;
}
ll i;
for(i=1;i*i<n;i++) if(n%i==0) v[++m]=i,v[++m]=n/i;
if(i*i==n) v[++m]=i;
P=2,A[1]=calc();
P=3,A[2]=calc();
P=4679,A[3]=calc();
P=35617,A[4]=calc();
P=999911658;
ans=(ans+P/2*work(P/2,2,A[1]))%P;
ans=(ans+P/3*work(P/3,3,A[2]))%P;
ans=(ans+P/4679*work(P/4679,4679,A[3]))%P;
ans=(ans+P/35617*work(P/35617,35617,A[4]))%P;
printf("%lld",pm(G,(ans+P)%P,P+1));
return 0;
}