\(\textrm{luogu P2480 [SDOI2010]古代猪文}\)
所以说嘛，我现在才刚入数论的门。
简要题意：
求 \(\large g^{\sum_{d \mid n}\binom{n}{d}}\) 在模 \(999911659\) 意义下的值。（以下简记为 \(mod\)）
- 欧拉定理
检测到 \(mod\) 为素数，于是有 \(\gcd(g,mod) = 1\)，可以考虑使用欧拉定理。
欧拉定理：
\[\gcd(a,n) = 1 \implies a^n \equiv a^{n \bmod {\varphi(n)}} \pmod n \]
由于 \(mod\) 为素数，故 \(\varphi(mod) = mod-1\)。
于是原题等价于求解 \(g^{\sum_{d \mid n}\binom{n}{d} \bmod {mod-1}} \bmod mod\)。
- 卢卡斯定理
现在发现求 \(\binom{n}{d}\) 时肯定不能直接 \(\mathcal{O}(n)\) 求，不然就爆了。
尝试卢卡斯定理：
\[p \in prime \implies \binom{n}{m} \equiv \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p \right\rfloor} \times \binom{n \bmod p}{m \bmod p} \pmod p \]
- 中国剩余定理
发现 \(mod-1 = 999911658\) 有点大了不是？何况也不是质数，总不能打一份扩展卢卡斯罢。
尝试唯一分解：\(999911658 = 2 \times 3 \times 4679 \times 35617\)。
所以我们先求出 \(\sum_{d \mid n}\binom{n}{d}\) 在模 \(2,3,4679,35617\) 意义下的值 \(a_i,a_2,a_3,a_4\)。
最后用中国剩余定理：
合并成其在模 \(999911658\) 意义下的值。
对了，记得防爆 long long。
#include <iostream>
typedef long long llt;
const llt mod = 999911659;
const int lmod[4] = {2,3,4679,35617};
llt quick_multi(llt _a,llt n,llt p) {
llt _res = 0ll;
while(n) {
if(n&1) {
_res += _a;
if(_res >= p)
_res -= p;
}
_a <<= 1;
if(_a >= p)
_a -= p;
n >>= 1;
}
return _res;
}
int quick_pow(int _a,int n,int p) {
int _res = 1;
while(n) {
if(n&1)
_res = 1ll*_res*_a%p;
_a = 1ll*_a*_a%p;
n >>= 1;
}
return _res;
}
llt defend_pow(llt _a,llt n,llt p) {
llt _res = 1ll;
while(n) {
if(n&1)
_res = quick_multi(_res,_a,p);
_a = quick_multi(_a,_a,p);
n >>= 1;
}
return _res;
}
int fact[35620], inv[35620];
int a[4];
void init(int p) {
fact[0] = inv[0] = 1;
for(int i = 1;i < p;++i)
fact[i] = 1ll*fact[i-1]*i%p;
inv[p-1] = quick_pow(fact[p-1],p-2,p);
for(int i = p-2;i >= 1;--i)
inv[i] = 1ll*inv[i+1]*(i+1)%p;
}
int C(int n,int m,int p) {
if(n < m||n < 0||m < 0)
return 0;
return 1ll*fact[n]*inv[m]%p*inv[n-m]%p;
}
int Lucas(int n,int m,int p) {
if(n < m)
return 0;
if(!n)
return 1;
return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
llt ans;
void CRT() {
for(int i = 0;i < 4;++i)
ans = (ans+a[i]*((mod-1)/lmod[i])%(mod-1)*quick_pow(mod/lmod[i],lmod[i]-2,lmod[i]))%(mod-1);
}
int n, g;
int main() {
scanf("%d %d",&n,&g);
if(!(g%mod)) {
printf("0\n");
return 0;
}
for(int i = 0;i < 4;++i) {
init(lmod[i]);
int d = 1;
for(;d*d < n;++d)
if(!(n%d)) {
a[i] += Lucas(n,d,lmod[i])+Lucas(n,n/d,lmod[i]);
while(a[i] >= lmod[i])
a[i] -= lmod[i];
}
if(d*d == n) {
a[i] += Lucas(n,d,lmod[i]);
if(a[i] >= lmod[i])
a[i] -= lmod[i];
}
}
CRT();
printf("%lld\n",defend_pow(g,ans,mod));
return 0;
}