HZOJ
洛谷
写在前面
挺久没写过单独的题解了,然后遇到这道做法挺神奇的题,就是那种让人眼前一亮的方法,遂打算写写。
题意
给出两个数\(n, g\),求问
\[g^{\sum_{x|n}~\binom{n}{x}}~mod~P~~(P=999911659)
\]
的值。
思路
首先组合数的和一定很大,所以考虑对其取模。组合数在幂次的位置,所以需要考虑用扩展欧拉定理降幂。\(P\) 是个质数,所以$$ g^k ~ mod ~ P = g^{k ~ mod ~ 𝜑(P)}~ mod P$$。然后与\(P\) 互质的数有\(P-1\) 个,所以\(𝜑(P)=P-1\)。
但是无法使用卢卡斯定理或扩展卢卡斯定理,我们考虑将模数分解,然后使用中国剩余定理求模数。
\(𝜑(P)\) 可分解为4个较小的质数,我们分别求出组合数模这几个质数的值,再使用CRT,就能解出组合数在模P意义下的数了。然后快速幂即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int mod=999911659,o=999911658,maxn=1e6;
int n,g;
int tot,k[maxn];
int jc[5][maxn],ny[5][maxn],fans[5];
inline int qpow(int x,int y,int p){if(x==0) return 0;int res=1;while(y){if(y&1) res=1ll*res*x%p;x=1ll*x*x%p;y>>=1;}return res;
}
inline int C(int x,int y,int p){if(x<y) return 0;return 1ll*jc[p][x]*ny[p][y]%k[p]*ny[p][x-y]%k[p];
}
inline int lucas(int x,int y,int p){if(!y) return 1;return 1ll*lucas(x/k[p],y/k[p],p)*C(x%k[p],y%k[p],p)%k[p];
}
int main(){cin>>n>>g;if(g==mod) cout<<0,exit(0);int p=o;for(int i=2;i*i<=p;i++)if(p%i==0){k[++tot]=i;while(p%i==0) p/=i;}if(p>1) k[++tot]=p;for(int i=1;i<=tot;i++){jc[i][0]=ny[i][0]=1;for(int j=1;j<k[i];j++) jc[i][j]=1ll*jc[i][j-1]*j%k[i],ny[i][j]=qpow(jc[i][j],k[i]-2,k[i]);}vector<int> ys;for(int i=1;i*i<=n;i++)if(n%i==0){ys.emplace_back(i);if(i*i!=n) ys.emplace_back(n/i);}for(int i=1;i<=tot;i++)for(int j:ys) fans[i]=(fans[i]+lucas(n,j,i))%k[i];int ans=0;for(int i=1;i<=tot;i++){int p=o/k[i];ans=(ans+1ll*fans[i]*p%o*qpow(p,k[i]-2,k[i])%o)%o;}cout<<qpow(g,ans,mod);return 0;
}