【题目地址】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1951

【题目大意】
PS.此题的题目描述是亮点，膜拜ipig~

“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……”
——选自猪王国民歌


给出N,G
求
G^( sigma(C(N,i) )   % P

i 满足 i | N

P = 999911659

【解题思路】
1. P 为素数
2. Phi(P) = P - 1 为square - free 数
3. 由于mod P,并且P 为素数，于是可以将指数直接mod Phi(P), 利用的是mod 素数的指数循环节开始位置必然为0 (具体见本人以前的文章)


于是问题就转化为组合数
由于N 比较小 (N <= 10 ^9)
于是可以分别计算c(N,i) % Pi
Pi 为 P - 1 的因子,容易知道 max{Pi} 很小
于是可以利用lucas定理求解
得到结果以后使用中国剩余定理合并即可(CRT)

于是问题就完美解决了,不过本人写的比较疵，且第一次提交忘记了一个可能溢出的细节，于是2Y,并跑了700+ MS....(卡过~)

【程序代码】
  1#include<iostream>
  2#include<stdio.h>
  3#include<string.h>
  4#include<cmath>
  5#include<map>
  6#include<string>
  7#include<algorithm>
  8#include<vector>
  9
 10using namespace std;
 11
 12typedef long long LL;
 13
 14const int maxn = 36000;
 15int f[4][maxn];
 16
 17int b[5] = {0,0,0,0};
 18int w[5] = {2,3,4679,35617};
 19const int P = 999911659;
 20int N,G;
 21
 22int ext_gcd(int a, int b, int &x, int &y){
 23    int t, d;
 24    if (! b) { x = 1; y = 0; return a; }
 25    d = ext_gcd(b, a % b, x, y);
 26    t = x;
 27    x = y;
 28    y = t - a / b*y;
 29    return d;
 30}
 31int China(int b[], int w[], int k) {
 32    int i;
 33    int d, x, y, m, n = 1;
 34    LL a = 0;
 35    for (i = 0; i < k; i++) n *= w[i];
 36    for (i = 0; i < k; i++) {
 37        m = n / w[i];
 38        d = ext_gcd(w[i], m, x, y);
 39        a = (a + (LL)y * m * b[i]) % n;
 40    }
 41    if (a > 0) return a;
 42    return (a + n);
 43}
 44
 45int s[2][101];
 46
 47int powmod(LL a,int b,int c){
 48    LL ret = 1;
 49    while(b){
 50        if(b & 0x1) ret = ret * a % c;
 51        a = a * a % c;
 52        b >>= 1;
 53    }
 54    return ret;
 55}
 56int cnk(int n,int k,int cur){
 57    int ans = f[cur][n],p = w[cur];
 58    ans = ans * powmod(f[cur][k],p - 2, p) % p;
 59    ans = ans * powmod(f[cur][n - k],p - 2, p) % p;
 60    return ans;
 61}
 62
 63int C(int n,int k,int cur){
 64    int i,x,len[2] = {0,0},c = 0,p = w[cur];
 65    x = n;
 66    while(x) s[0][len[0] ++] = x % p,x /= p;
 67    x = k;
 68    while(x) s[1][len[1] ++] = x % p, x/= p;
 69    while(len[1] < len[0]) s[1][len[1] ++] = 0;
 70    for(i = 0; i < len[0]; ++ i) if(s[1][i] > s[0][i]) return 0;
 71    int ans = 1;
 72    for(i = 0; i < len[0]; ++ i) ans = ans * cnk(s[0][i],s[1][i],cur) % p;
 73    return ans;
 74}
 75
 76int main(){
 77    int i,j;
 78    for(i = 0; i < 4; ++ i){
 79        f[i][0] = 1;
 80        for(j = 1; j < w[i]; ++ j)
 81            f[i][j] = f[i][j - 1] * j % w[i];
 82    }
 83    scanf("%d%d",&N,&G);
 84    if(G == P){
 85        puts("0");
 86        return 0;
 87    }
 88    G %= P;
 89    for(i = 1; i * i <= N; ++ i)
 90        if(N % i == 0){
 91            int x = i;
 92            b[0] = (b[0] + C(N,x,0)) % w[0];
 93            b[1] = (b[1] + C(N,x,1)) % w[1];
 94            b[2] = (b[2] + C(N,x,2)) % w[2];
 95            b[3] = (b[3] + C(N,x,3)) % w[3];
 96            x = N / i;
 97            if(i * i != N){
 98                b[0] = (b[0] + C(N,x,0)) % w[0];
 99                b[1] = (b[1] + C(N,x,1)) % w[1];
100                b[2] = (b[2] + C(N,x,2)) % w[2];
101                b[3] = (b[3] + C(N,x,3)) % w[3];
102            }
103        }
104        int ans = powmod(G,China(b,w,4),P);
105        printf("%d\n",ans);
106        return 0;
107}