题目链接
这题出的有点nb，PKU: Pig Kingdom University ， NOIP: National Olympics in Informatic of Pigs。。。
题意：求\(G^{\sum_{d|n}C_n^d}mod\ 999911659\)
根据费马小定理的推论，题目可以转化为求\(G^{\sum_{d|n}C_n^dmod999911658}mod\ 999911659\)
对\(999911658\)分解质因数可得\(999911658=2\times3\times4679\times35617\)
枚举这4个数，再枚举\(n\)的因子\(d\)，预处理阶乘和逆元，用Lucas定理求出\(\sum_{d|n}C_n^d\)，最后用中国剩余定理合并就行了。
#include <cstdio>
#include <cstdlib>
#include <cmath>
typedef long long ll;
const int MAXN = 40000; // The Biggest Prime
const int MOD = 999911659;
const int MO = 999911658;
const int prime[6] = {233, 2, 3, 4679, 35617};
const int M = 4;
int n, q;
int fact[MAXN], inv[MAXN], a[M + 2], t[M + 2];
int C(int n, int m, int mod){
if(n < m) return 0;
return fact[n] * inv[fact[m]] % mod * inv[fact[n - m]] % mod;
}
int Lucas(int n, int m, int mod){
if(!m) return 1;
return C(n % mod, m % mod, mod) * Lucas(n / mod, m / mod, mod) % mod;
}
int Pow(int q, int k, int mod){
int ans = 1;
while(k){
if(k & 1) ans = ((long long)ans * q) % mod;
k >>= 1;
q = (long long)q * q % mod;
}
return ans;
}
int Crt(int a[]){
int ans = 0;
for(int i = 1; i <= M; ++i){
int tmp = MOD / prime[i];
ans = ((long long)ans + (long long)a[i] * tmp % MO * Pow(tmp, prime[i] - 2, prime[i])) % MO;
}
return ans;
}
int main(){
scanf("%d%d", &n, &q);
if(q % MOD == 0){
printf("0\n");
return 0;
}
inv[1] = 1;
fact[1] = 1;
fact[0] = 1;
for(int i = 1; i <= M; ++i){
for(int j = 2; j <= prime[i]; ++j)
fact[j] = (fact[j - 1] * j) % prime[i], inv[j] = (prime[i] - prime[i] / j) * inv[prime[i] % j] % prime[i];
for(int d = 1; d * d <= n; ++d){
if(n % d) continue;
a[i] = (a[i] + Lucas(n, d, prime[i])) % prime[i];
if(d * d == n) continue;
a[i] = (a[i] + Lucas(n, n / d, prime[i])) % prime[i];
}
}
printf("%d\n", Pow(q, Crt(a), MOD));
return 0;
}