洛谷 P2480 [SDOI2010] 古代猪文 题解

形式化题意

给定 \(n,g\) 和模数 \(P=999911659\)（一个质数），求以下柿子的值。

\[g^{\sum_{i|n}C_n^i} \bmod P\]
知识点

扩展欧拉定理、Lucas 定理、中国剩余定理 CRT、exLucas 算法。
基础数论全家桶。
解法

发现指数会非常大，先用扩展欧拉定理缩小指数，得：

\[g^{\sum_{i|n}C_n^i} \equiv g^{\left(\sum_{i|n}C_n^i\right) \bmod (P-1)} \pmod P\]
现在考虑计算这个柿子：

\[\left(\sum_{i|n}C_n^i\right) \bmod (P-1)\]
于是 \(\mathcal{\Theta}(\sqrt n)\) 枚举 \(i\)，求出每个 \(C_n^i \bmod (P-1)\) 即可。
一个问题是，模数 \(P-1\) 不是质数，因此用不了 Lucas 定理。但是发现 \(P-1=2\cdot3\cdot4679\cdot35617\)，恰好是四个质数之积。于是可以分别用 Lucas 定理求出 \(C_n^i\) 对 \(2,3,4679,35617\) 取模的结果，然后 CRT 合并即可。这被称为 exLucas 算法。
注意特判 \(g=P\)。
Code

[code]#include #define rep(i,a,b) for(int i(a);ib;--i)#define rept(i,a,b) for(int i(a);i=b;--i)#define int long longusing namespace std;constexpr int P=999911659,N=4e4;constexpr int FAC[4]={2,3,4679,35617};constexpr int COEF[4]={499955829,333303886,289138806,877424796};// P-1=2*3*4679*35617// COEF为CRT的系数，预先计算好int fac[4][N],inv[4][N];int ksm(int x,int y,int m){    int res=1;    while(y){        if(y&1) (res*=x)%=m;        (x*=x)%=m,y>>=1;    }    return res;}int c(int m,int n,int k){    if(m>g;    rep(k,0,4){        fac[k][0]=inv[k][0]=1;        rep(i,1,FAC[k]) fac[k]=fac[k][i-1]*i%FAC[k];        inv[k][FAC[k]-1]=ksm(fac[k][FAC[k]-1],FAC[k]-2,FAC[k]);        pert(i,FAC[k]-2,1) inv[k]=inv[k][i+1]*(i+1)%FAC[k];    }    if(g%P==0){  // 特判        cout