C++ 代码
#include <cstdio>
typedef long long ll;
const int N = 5e4, MOD = 999911659;
ll n, q;
ll jc[N], a[5]; //记录余数
int pri[4] = {2, 3, 4679, 35617};
void init(int m) {
jc[0] = 1;
for (int i = 1; i <= m; i++) {
jc[i] = jc[i - 1] * i % m;
}
}
ll qpow(ll a, ll b, ll m) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % m;
a = a * a % m;
b >>= 1;
}
return ans;
}
ll C(ll n, ll d, ll m) {
if (n < d) return 0; //这里注意一下
return jc[n] * qpow(jc[d], m - 2, m) % m * qpow(jc[n - d], m - 2, m) % m;
}
ll lucas(ll n, ll d, ll m) {
if (n < m && d < m) {
return C(n, d, m);
}
return C(n % m, d % m, m) * lucas(n / m, d / m, m) % m;
}
ll CRT() {
ll ans = 0;
ll M = 999911658;
for (int i = 0; i < 4; i++) {
ll Mi = M / pri[i];
//由于mi是质数 所以可以直接用快速幂求
//ll t = (qpow(Mi, pri[i] - 2, pri[i]) % pri[i] + pri[i]) % pri[i] ;
ll t = qpow(Mi, pri[i] - 2, pri[i]);
ans = (ans + a[i] * Mi % M * t % M) % M;
}
return ans;
}
void f(ll n, ll q) {
for (ll k = 0; k < 4; k++) {
ll p = pri[k];
init(p);
//试除法求出所有的约数
for (ll i = 1; i <= n / i; i++) {
if (n % i == 0) {
a[k] = (a[k] + lucas(n, i, p)) % p;
if (i != n / i) {
a[k] = (a[k] + lucas(n, n / i, p)) % p;
}
}
}
}
ll x = CRT();
printf("%lld\n", qpow(q, x, MOD));
}
int main() {
scanf("%lld%lld", &n, &q);
if (q % MOD == 0) { //特判一下
printf("0\n");
} else {
f(n, q);
}
return 0;
}