目录
显示
题目链接
https://www.luogu.com.cn/problem/P2480
题解
容易看出本题要求的是:
$$
G^{\sum_{k\mid n}C_{n}^{k}} \bmod 999\ 911\ 659
$$
分两种情况讨论:
- \(G=999\ 911\ 659\),显然答案为 \(0\)。
- \(G\neq 999\ 911\ 659\),由欧拉定理可知,我们要求的是:
$$
G^{\sum_{k\mid n}C_{n}^{k} \bmod 999\ 911\ 658} \bmod 999\ 911\ 659
$$
所以我们重点考虑如何计算:
$$
\sum_{k\mid n}C_{n}^{k} \bmod 999\ 911\ 658
$$
因为 \(999\ 911 \ 658\) 不是质数,无法保证 \(\forall x \in [1,999\ 911\ 658]\),\(x\) 都有逆元存在,因此上面的式子我们无法直接按照组合数定义计算。
试着把模数分解一下,发现 \(999\ 911 \ 658=2 \times 3 \times 4679 \times 35617\),其中每个质因子的最高次数都为一。
这个性质启发我们求出 \(\sum_{k\mid n}C_{n}^{k}\) 分别对 \(2\),\(3\),\(4679\),\(35617\) 取模的结果,最后利用 中国剩余定理 合并结果。
也就是说,我们实际上要求下面一个线性方程组的解:
$$
\begin{cases}
x \equiv a_1 \pmod 2\\
x \equiv a_2 \pmod 3\\
x \equiv a_3 \pmod {4679}\\
x \equiv a_4 \pmod {35617}
\end{cases}
$$
而计算一个组合数对较小的质数取模后的结果,可以利用 卢卡斯定理。
// Problem : P2480 [SDOI2010]古代猪文 // Contest : Luogu // URL : https://www.luogu.com.cn/problem/P2480 // Memory Limit : 125 MB // Time Limit : 1000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #include <cstring> #include <iostream> #define MOD 999911658 using namespace std; //999911658=2*3*4679*35617 const int p[]={0,2,3,4679,35617}; int n,g; long long f[50005],invf[50005]; long long fpow(long long x,long long y,long long p) { long long ans=1; while(y) { if(y&1)ans=ans*x%p; x=x*x%p; y>>=1; } return ans; } long long C(int x,int y,int p) { if(x<y)return 0; return f[x]*invf[y]%p*invf[x-y]%p; } long long Lucas(int x,int y,int p) { if(x==0)return 1; return C(x%p,y%p,p)*Lucas(x/p,y/p,p)%p; } long long calc(int p) { f[0]=invf[0]=1; for(int i=1;i<p;i++) f[i]=f[i-1]*i%p; invf[p-1]=fpow(f[p-1],p-2,p); for(int i=p-2;i;i--) invf[i]=invf[i+1]*(i+1)%p; long long sum=0; for(int i=1;i*i<=n;i++) if(n%i==0) { sum=(sum+Lucas(n,i,p))%p; if(i*i!=n)sum+=(Lucas(n,n/i,p))%p; } return sum; } int main() { cin>>n>>g; long long ans=0; if(g==MOD+1) { cout<<0<<endl; return 0; } for(int i=1;i<=4;i++) { long long x=calc(p[i]),y=MOD/p[i],invy=fpow(y,p[i]-2,p[i]); ans=(ans+x*y%MOD*invy)%MOD; } cout<<fpow(g,ans,MOD+1)<<endl; return 0; }