这道题是各种数论搞在一起的题目。。。
首先由burnside引理可以知道答案是ans = (G^sigma(C(n, d))) % MOD
然后由费马小定理，ans = (G^（sigma(C(n, d)) % (MOD - 1)）) % MOD
之后把MOD - 1分解为2 * 3 * 4679 * 35617，用Lucas定理分别求出sigma(C(n, d)) % m，其中m = 2, 3, 4679, 35617
最后再用中国剩余定理合起来快速幂一下就好辣！
1 /************************************************************** 2 Problem: 1951 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:76 ms 7 Memory:2772 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 13 using namespace std; 14 typedef long long LL; 15 const LL p = 999911659; 16 const int x[4] = {2, 3, 4679, 35617}; 17 18 LL mod[4][50000], a[50000], b[5], cnt, n, g, y, z; 19 20 inline LL pow(LL a, LL b, LL p){ 21 LL res = 1; 22 while (b){ 23 if (b & 1) res *= a, res %= p; 24 a *= a, a %= p; 25 b >>= 1; 26 } 27 return res; 28 } 29 30 LL extend_gcd(int a, int b, LL &x, LL &y){ 31 if (!b){ 32 x = 1, y = 0; 33 return a; 34 } 35 LL res = extend_gcd(b, a % b, y, x); 36 y -= a / b * x; 37 return res; 38 } 39 40 inline LL GCD(int a, int p){ 41 LL x, y, d = extend_gcd(a, p, x, y); 42 while (x < 0) x += p; 43 return x; 44 } 45 46 inline LL C(int i, int n, int k, int p){ 47 return mod[i][n] * GCD(mod[i][n - k] * mod[i][k] % p, p) % p; 48 } 49 50 inline LL Lucas(int i, int n, int k, int p){ 51 LL res = 1; 52 while (n && k){ 53 res *= C(i, n % p, k % p, p), res %= p; 54 if (!res) return 0; 55 n /= p, k /= p; 56 } 57 return res; 58 } 59 60 inline LL Chinese(){ 61 LL M = 1, res = 0; 62 for (int i = 0; i < 4; ++i) M *= x[i]; 63 for (int i = 0; i < 4; ++i){ 64 LL w = M / x[i], x1, y1, d = extend_gcd(w, x[i], x1, y1); 65 res += x1 * w * b[i], res %= M; 66 } 67 return (res + M) % M; 68 } 69 70 int main(){ 71 scanf("%lld%lld", &n, &g); 72 g %= p; 73 if (!g){ 74 printf("0 "); 75 return 0; 76 } 77 for (int i = 0; i < 4; ++i){ 78 mod[i][0] = 1; 79 for (int j = 1; j <= x[i]; ++j) 80 mod[i][j] = (mod[i][j - 1] * j) % x[i]; 81 } 82 int maxi = (int) sqrt(n); 83 for (int i = 1; i <= maxi; ++i) 84 if (!(n % i)){ 85 a[++cnt] = i; 86 if (i * i != n) a[++cnt] = n / i; 87 } 88 89 for (int i = 1; i <= cnt; ++i) 90 for (int j = 0; j < 4; ++j){ 91 b[j] += Lucas(j, n, a[i], x[j]); 92 if (b[j] > x[j]) b[j] -= x[j]; 93 } 94 int z = Chinese(); 95 printf("%lld ", pow(g, z, p)); 96 return 0; 97 }