好像数学都退化了。
其实一直没有用过中国剩余定理。虽然好像也不是太麻烦，不过要记住。
然后这题也比较裸吧。把C(n,m)中的阶乘分解成t*p^k的样子就好了。ORZ JASON_YU
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long qw;
#define _l (qw)
const int mod = 999911659;
const int pn[4] = {2, 3, 4679, 35617};
const int maxb = 50009;
int n, g, fac[maxb], tf, s[4];
int t[maxb];
int modPow(int a, int x, int mod) {
int s = 1;
for (a %= mod; x; x >>= 1, a = _l a * a % mod)
if (x & 1)
s = _l s * a % mod;
return s;
}
void gfac(int n, int& t0, int& k0, int d, int p) {
int tt = _l modPow(t[p - 1], n / p, p) * t[n % p] % p;
int kk = 0;
for (qw pp = p; pp <= n; pp *= p) {
tt = _l tt * modPow(t[p - 1], n / pp / p, p) % p * t[(n / pp) % p] % p;
kk += n / pp;
}
k0 += kk * d;
if (d == 1)
t0 = _l t0 * tt % mod;
else
t0 = _l t0 * modPow(tt, p - 2, p) % p;
}
int calc(int pn) {
int ans = 0;
t[0] = 1;
t[1] = 1;
for (int i = 2; i < pn; ++ i)
t[i] = _l t[i - 1] * i % pn;
for (int i = 0; i < tf; ++ i) {
int t0 = 1, k0 = 0;
gfac(n, t0, k0, 1, pn);
gfac(fac[i], t0, k0, -1, pn);
gfac(n - fac[i], t0, k0, -1, pn);
if (!k0)
ans = (ans + t0) % pn;
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &g);
if (g == mod) {
puts("0");
return 0;
}
tf = 0;
for (int i = 1; i * i <= n; ++ i)
if (n % i == 0) {
fac[tf ++] = i;
if (i * i < n)
fac[tf ++] = n / i;
}
qw ans = 0;
for (int i = 0; i < 4; ++ i) {
s[i] = calc(pn[i]);
int mt = (mod - 1) / pn[i];
ans = (ans + _l s[i] * mt % (mod - 1) * modPow(mt, pn[i] - 2, pn[i]) % (mod - 1)) % (mod - 1);
}
printf("%d\n", modPow(g, ans, mod));
}