Link:https://www.lydsy.com/JudgeOnline/problem.php?id=1951
Solution:
见过最长的数论题题面.......
一道数论的综合题，求解：
\[g^{\sum_{d|n} C_n^d}~mod~p\]
我们先看幂能否化简，
由费马小定理可知：
\begin{aligned} \displaystyle ans &= g^{\sum_{d|n} C_n^d}~mod~p \\ &=g^{\sum_{d|n} C_n^d~mod~(p-1)}~mod~p \end{aligned}
对于化简后的幂：
\[\sum_{d|n} C_n^d~mod~(p-1)\]
我们想到枚举每一个n的约数，使用Lucas定理求大组合数取模
但P-1=2*3*4679*35617，不是一个质数
于是我们以每一个质因子为模数算出最终的解
由于质因子之间是互质的，再用中华剩余定理合并结果算出最小的\[\sum_{d|n} C_n^d\]，即为\[\sum_{d|n} C_n^d~mod~(p-1)\]
Code:
#includeusing namespace std;typedef long long ll;const int MAXN=1e5+10;const int MOD=999911659;int quick_pow(ll a,ll b,int p) //快速幂{ ll ret=1;a%=p; while(b) { if(b&1) ret=ret*a%p; b>>=1;a=a*a%p; } return ret; } int inv(ll a,int p){return quick_pow(a,p-2,p);} //求逆元 int g,n,fac[4][MAXN],c[4]; int pri[]={2,3,4679,35617}; int C(int n,int m,int p) //求组合数 { if(n>m) return 0; return 1ll*fac[p][m]*inv(1ll*fac[p][n]*fac[p][m-n],pri[p])%pri[p]; } int Lucas(int n,int m,int p) //Lucas定理 { if(m==0) return 1; return C(n%pri[p],m%pri[p],p)*Lucas(n/pri[p],m/pri[p],p)%pri[p]; } ll CRT() //中国剩余定理 { ll ret=0,p=MOD-1; for(int i=0;i<4;i++) ret=(ret+1ll*p/pri[i]*inv(p/pri[i],pri[i])*c[i])%p; return ret%MOD; } int main() { cin >> n >> g; if(g==MOD) return cout << 0,0; for(int i=0;i<4;i++) //预处理阶乘 { fac[i][0]=1; for(int j=1;j<=pri[i];j++) fac[i][j]=fac[i][j-1]*j%pri[i]; } for(int i=0;i<4;i++) for(int j=1;j*j<=n;j++) if(n%j==0) { c[i]=(c[i]+Lucas(j,n,i))%pri[i]; if(j*j!=n) c[i]=(c[i]+Lucas(n/j,n,i))%pri[i]; } cout << quick_pow(g,CRT(),MOD); return 0; }
Review:
1、如果模数为质数，
利用费马小定理对幂化简
2、遇到大组合数取模 -------> Lucas定理
如果模数不为质数，质因数分解后分别求出结果再用中华剩余定理合并，套路啊……
3、中华剩余定理求解方法
（1）递推式地两两求解
（2）根据推导出的结论直接求解：
\[x=(\sum\limits_{i=1}^k c_i*{M\over m_i}*inv({M\over m_i},mi))\%M\]