「数論~ 数論~ 数論~ 数論~ 数論大家族」
关于本题
这是一道数论大杂烩模法题，题目叙述及其冗长，真正有用的其实就只有两句话。题目压缩后可以表述为求
$\LARGE g^{\Sigma_{k|n}C^{\frac{n}{k}}_{n}}\bmod 999911659$
解答本题你需要至少会使用以下结论和定理：
本题中用到的部分还会在下文讲述。
本题中用到的结论与定理
欧拉定理推论
欧拉定理内容为：若正整数 $a,n$ 互质，则有 $a^{\varphi(n)}\equiv 1(\bmod p)$，其中 $\varphi(n)$ 为欧拉函数
我们在这道题中使用的是欧拉定理的推论：若正整数 $a,n$ 互质，则对于任意正整数 $b$ 有 $a^{b}\equiv a^{b\bmod\varphi(n)}(\bmod n)$.
可以简单地证明：设 $b=q*\varphi(n)+r,(0\le r\le \varphi(n))$，即 $r=b \bmod \varphi(n)$。于是有：
$\large a^{b} \equiv a^{q*\varphi(n)+r} \equiv (a^{\varphi(n)})^{q}a^{r} \equiv 1^qa^r \equiv a^r \equiv a^{b \bmod \varphi(n)}(\bmod n)$
其中第三步使用了欧拉定理。
中国剩余定理
设 $m_1,m_2,…,m_n$ 是两两互素的整数，$m=\Pi^{n}{i=1}m_i$，$M_i=\frac{m}{m_i}$，$t_i$ 是线性同余方程 $M_it_i \equiv 1(\bmod m_i)$ 的一个解。对于任意的 $n$ 个整数 $a_1,a_2,…,a_n$，方程组 $$ \begin{cases} x \equiv a_1(\bmod m_1)\ x \equiv a_2(\bmod m_2)\ …\ x \equiv a_n(\bmod m_n)\ \end{cases} $$ 有整数解，为 $\large x=\Sigma^n{i=1}a_iM_it_i$.
由于鄙人太菜，无法证明，所以请各位大神出门左转 OI Wiki $Q w Q$
Lucas 定理
若 $p$ 是素数，则对于任意整数 $1 \le m \le n$，有 $\large C^m_n \equiv C^{m \bmod p}{n \bmod p}*C^{m/p}{n/p}(\bmod p)$
原理是把 $n$ 和 $m$ 表示成 $p$ 进制数，对 $p$ 进制下每一位分别计算组合数，最后再乘起来。由于鄙人太菜，无法证明，所以请各位大神出门右转 OI Wiki $Q w Q$
思路
因为有 $k |n$，所以在求和时 $\frac{k}{n}$ 和 $k$ 都会被算到，原式中的 $C^{\frac{k}{n}}_{n}$ 可以变为 $C^k_n$，虽然并没有使式子变简单但是看起来更舒服。
根据欧拉定理的推论有 $\large g^{\Sigma_{k|n}C^{k}{n}}\equiv g^{\Sigma{k|n}C^{k}{n}\bmod999911658}(\bmod 999911659)$，快速地写一个简单小程序，就可以判断出模数 999911659 是一个素数，所以右边的 $\varphi(999911659)=999911658$，于是，本题的关键在于 $ \Sigma{k|n}C^{k}_{n}\bmod999911658$ 的计算。
聪敏的你一定会想到使用 Lucas 定理进行组合数取模计算，但是 Lucas 定理要求模数是一个小素数，显然我们现在的模数 999911658 并不是一个小素数——它甚至不是一个素数！还有一个 exLucas 定理仿佛可以使用，但是比较难，又会引入更多的结论和定理了。
若有正整数 $a,b$ 满足 $a \bmod b =r$ 且 $b=mn$，那么一定有 $a \bmod m=a \bmod n=r$。这是显然的——根据题意,设 $a=qb+r$，于是 $a=qmn+r$。根据这条结论，我们可以将模数 999911658 分解素因子，并使用中国剩余定理列出同余方程组。通过简单的函数可以分解模数为 $999911658=234679*35617$，于是有方程组： $$ \begin{cases} x \equiv \Sigma_{k|n}C^{k}{n}(\bmod 2)\ x \equiv \Sigma{k|n}C^{k}{n}(\bmod 3)\ x \equiv \Sigma{k|n}C^{k}{n}(\bmod 4679)\ x \equiv \Sigma{k|n}C^{k}{n}(\bmod 35617)\ \end{cases} $$ 如果可以解出 $x$，便有 $x=\Sigma{k|n}C^{k}_{n}\bmod999911658$。对于其中的每一个线性同余方程，模数都变成了一个较小的素数，我们可以利用 Lucas 定理对组合数取模。由于题目中 $n$ 的范围比较大，所以我们可以预处理每个数的阶乘以及阶乘的逆元，于是就可以更快的求组合数了。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MaxN=500005, Mod=999911659;
ll n, g, k[MaxN];
ll factorial_of[MaxN], inverseofFctorial_of[MaxN];
ll singleLeft[5], primeFactor[5], primeCount, factorCount, finalPowerTimes;
inline ll QuickPower(ll baseNumber,ll powerTimes,ll mod){
ll answer = 1;
while(powerTimes){
if(powerTimes & 1) answer = answer * baseNumber % mod;
baseNumber = baseNumber * baseNumber % mod;
powerTimes >>= 1;
}
return answer % mod;
}
inline void Init(ll mod){
factorial_of[0] = 1;
for(int i=1;i<mod;i++)
factorial_of[i] = factorial_of[i-1] * i % mod;
inverseofFctorial_of[mod] = 0;
inverseofFctorial_of[mod - 1] = QuickPower(factorial_of[mod-1], mod - 2, mod);
for(int i=mod-2;i>=0;i--)
inverseofFctorial_of[i] = inverseofFctorial_of[i+1] * (i+1) % mod;
}
inline ll C(ll x,ll y,ll mod){
if(y > x) return 0;
return factorial_of[x] * inverseofFctorial_of[y] % mod * inverseofFctorial_of[x-y] % mod;
}
inline ll Lucas(ll x,ll y,ll mod){
if(y == 0) return 1;
return Lucas(x / mod, y / mod, mod) * C(x % mod, y % mod, mod) % mod;
}
inline ll SingleLineCalculation(int x){
Init(primeFactor[x]);
for(int i=1;i<=factorCount;i++)
singleLeft[x] = (singleLeft[x] + Lucas(n, k[i], primeFactor[x])) % primeFactor[x];
}
inline ll CRT(){
ll answer = 0, mod = Mod-1;
for(int i=1;i<=primeCount;i++){
ll M = mod / primeFactor[i], t = QuickPower(M, primeFactor[i]-2, primeFactor[i]);
answer = (answer + (singleLeft[i] % mod) * (t % mod) * (M % mod)) % mod;
}
return (answer + mod) % mod;
}
inline void GetPrimeFactor(ll originalNumber){
for(int i=2;i*i<=Mod-1;i++){
if(originalNumber % i == 0){
primeFactor[++primeCount] = i;
while(originalNumber % i == 0) originalNumber /= i;
}
}
if(originalNumber != 1) primeFactor[++primeCount] = originalNumber;
}
inline void GetK(){
for(int i=1;i*i<=n;i++){
if(n % i == 0){
k[++factorCount] = i;
if(i * i != n) k[++factorCount] = n / i;
}
}
}
int main(){
scanf("%lld%lld", &n, &g);
if(g % Mod == 0){
printf("0");
return 0;
}//remember to add a special judge, or you will lose 5 pts
GetPrimeFactor(Mod - 1);
GetK();
for(int i=1;i<=primeCount;i++) SingleLineCalculation(i);
finalPowerTimes = CRT();
printf("%lld", QuickPower(g, finalPowerTimes, Mod));
return 0;
}