标签：数论，Lucas定理，CRT，快速幂
题目
计算\(G^{\sum_{i\|n} C(n,i)} \% P\)
\(100\%\)的数据中，\(1\leq G\leq 1000000000，1\leq N \leq 1000000000\)
分析
根据费马小定理，指数可以变成
\[\sum_{i|n} C(n,i)\%(P-1)\]然后可以使用Lucas定理快速求组合数，之后用快速幂求出答案
999911659的约数有2,3,4679,35617，分别对这四个约数求组合数，之后使用CRT合并
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//******head by yjjr******
#define mod 999911659
const int maxn=4e5+6;
int g,n,m[4],fac[4][maxn];
int t[4]={2,3,4679,35617};
inline ll qpow(ll a,ll b,int p){
ll re=1;
while(b){
if(b&1)re=(ll)(re*a)%p;
b>>=1,a=(ll)(a*a)%p;
}
return re;
}
inline ll C(int n,int m,int x){
if(n<m)return 0;
return (ll)(1ll*fac[x][n]*qpow(fac[x][n-m]*fac[x][m],t[x]-2,t[x])%t[x]);
}
inline ll Lucas(int n,int m,int x){
if(m==0)return 1;
return (ll)(1ll*C(n%t[x],m%t[x],x)*Lucas(n/t[x],m/t[x],x)%t[x]);
}
void exgcd(int a,int b,int &x,int &y){
if(b==0){x=1,y=0;return;}
exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
}
inline ll solve(){
int a1,b1,a2,b2,a,b,c,x,y;
a1=t[0],b1=m[0];
rep(i,1,3){
a2=t[i],b2=m[i];
a=a1,b=a2,c=b2-b1;
exgcd(a,b,x,y);
x=((x*c)%b+b)%b;
b1=b1+a1*x;
a1=a1*b;
}
return b1;
}
int main(){
rep(i,0,3){
fac[i][0]=1;
rep(j,1,t[i])fac[i][j]=(fac[i][j-1]*j)%t[i];
}
n=read(),g=read();
if(g==mod){puts("0");return 0;}
g%=mod;
for(int i=1;i*i<=n;i++)
if(n%i==0){
int tmp=n/i;
rep(j,0,3){
if(tmp!=i)m[j]=(m[j]+Lucas(n,i,j))%t[j];
m[j]=(m[j]+Lucas(n,tmp,j))%t[j];
}
}
cout<<qpow(g,solve(),mod)<<endl;
return 0;
}
