laekov

好像数学都退化了。

其实一直没有用过中国剩余定理。虽然好像也不是太麻烦，不过要记住。

然后这题也比较裸吧。把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));

}