已经交了11发了

CRT合并解，我对于每个组合数都用一次CRT计算组合数取模后的值/kk/kk/kk/kk/kk

#include <iostream>
#define int long long

const int MOD = 999911659LL;
const int f[] = {2, 3, 4679, 35617};
int fact[36000];
int qpow(int a, int b, int mod) {
	int ret(1LL);
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
void exgcd(const int a, const int b, int& x, int &y) {
	if (!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(const int a, const int mod) {
	int x, y;
	exgcd(a, mod, x, y);
	return (x % mod + mod) % mod;
}
inline int C(const int n, const int m, const int p) {
	if (n < m) return 0LL;
	return fact[n] * inv(fact[m], p) % p * inv(fact[n - m], p);
}
inline int Lucas(const int n, const int m, const int p) {
	if (n < m) return 0LL;
	return m == 0 ? 1 : C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
inline int CRT(int n, int m) {
	int sum(MOD - 1), ans(0LL);
	for (int i(0); i <= 3; ++ i) {
		int t(sum / f[i]);
		ans = (ans + Lucas(n, m, f[i]) * t % sum * inv(t, f[i]) % sum) % sum;
	}
	return ans;
}

signed main() {
	fact[0] = 1LL;
	int n, g, ans(0LL);
	std::cin >> n >> g;
	if (g == MOD) return putchar('0'), 0;
	for (int i(1); i <= 35617; ++ i) fact[i] = fact[i - 1] * i % MOD;
	for (int i(1); i * i <= n; ++ i) if (n % i == 0) {
		ans = (ans + CRT(n, i)) % (MOD - 1LL);
		if (i * i != n) ans = (ans + CRT(n, n / i)) % (MOD - 1LL);
	}
	std::cout << qpow(g, (ans + MOD - 1LL) % (MOD - 1LL), MOD);
	return 0;
}