[SDOI2010]古代猪文
题目大意：
给定 \(n,g\) ，求：
\[g^{\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}}\bmod 999911659
\]
solution：
模数是质数，有费马小定理，原式变为：
\[g^{\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 999911658}\bmod 999911659
\]
但直接通过 \(\text{Lucas}\) 定理计算组合数也不被允许，所以我们把 \(999911658\) ，分解下质因数：\(999911658=2\times 3\times 4679\times 35617\) 。
我们设 \(a_1=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 2,a_2=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 3,a_3=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 4679,a_4=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 35617\) 。
对于 \(g\) 的幂次 \(p\) ，有：
\[\begin{cases}
p\equiv a_1 \pmod 2\p\equiv a_2 \pmod 3\p\equiv a_3 \pmod {4679}\p\equiv a_4 \pmod {35617}
\end{cases}\]
用 \(\text{CRT}\) 求解即可。
细节处理：
- 对于 \(g=999911659\) 要进行特判，因为此时 \(g\) 的几次幂都不可能为 \(0\) ，而此时答案显然为 \(0\) 。
代码
#include<cstdio>
using namespace std;
typedef long long LL;
const int N=40000,mod=999911659,M=999911658;
int a[5],mi[5]={0,2,3,4679,35617};
int fac[N],inv[N];
inline int qpow(int x,int b,int p){
int res=1;
while(b){
if(b&1) res=(LL)res*x%p;
x=(LL)x*x%p;
b>>=1;
}
return res;
}
inline void Fac(int p){
fac[0]=1;
for(int i=1;i<=p;i++)//实际上到 p-1 即可
fac[i]=(LL)fac[i-1]*i%p;
}
inline void Inv(int p){
inv[p-1]=qpow(fac[p-1],p-2,p);//需要用 fac[p-1] 往回推。
for(int i=p-2;i>=0;i--)
inv[i]=(LL)inv[i+1]*(i+1)%p;
}
inline int C(int n,int m,int p){
if(n<m) return 0;//此处特判
return (LL)fac[n]*inv[m]%p*inv[n-m]%p;
}
inline int Lucas(int n,int m,int p){
if(!m) return 1;//特判
return (LL)C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
inline void div(int n){
for(int i=1;i<=4;i++){
Fac(mi[i]),Inv(mi[i]);
for(int j=1;j<=n/j;j++){//n/j防止越界
if(n%j!=0) continue;
a[i]=((LL)a[i]+Lucas(n,j,mi[i]))%mi[i];
if((LL)j*j!=n)
a[i]=((LL)a[i]+Lucas(n,n/j,mi[i]))%mi[i];
}
}
}
inline int CRT(){
int ans=0;
for(int i=1;i<=4;i++){
int Mi=M/mi[i];
int t=qpow(Mi,mi[i]-2,mi[i]);//费马小定理求逆元
ans=((LL)ans+(LL)a[i]*Mi%M*t%M)%M;
}
return ans;
}
int main(){
int n,g; scanf("%d%d",&n,&g);
if(g%mod==0) return puts("0"),0;//特判
div(n);//求约数 O(sqrt(n))
int p=CRT();//中国剩余定理和并解
printf("%d",qpow(g,p,mod));
return 0;
}