[洛谷 2480,loj 10229][SDOI2010]古代猪文

题目链接

https://www.luogu.com.cn/problem/P2480

https://loj.ac/problem/10229

题解

容易看出本题要求的是：

$$
G^{\sum_{k\mid n}C_{n}^{k}} \bmod 999\ 911\ 659
$$

分两种情况讨论：

1. \(G=999\ 911\ 659\)，显然答案为 \(0\)。
2. \(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;
}