分析

读完题，我们发现就是求 。因为 是一个素数，那么我们根据欧拉定理 。那么我们其实就是求 。好像到这里我们没法快速计算组合数了，可以考虑 定理，但是 并不是一个素数。那么我们先考虑唯一分解，对于 的每个素因子，发现最大的素因子才 ，最后在通过中国剩余定理合并。时间复杂度为 。

代码

#include<bits/stdc++.h> 
using namespace std;
#define LL long long
#define int long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 4e6 + 100;
LL mod[6] = {999911659,2,3,4679,35617};
LL g,n,fac[N][6],A[6];
LL qpow(LL a,LL b,LL p) {
    LL x = 1;
    for(;b;b>>=1,a = a * a % p) {
        if(b&1) x = x * a % p;
    }
    return x;
}
LL C(LL a,LL b,LL p) {
    if(b > a) return 0;
    return fac[a][p] * qpow(fac[a-b][p],mod[p]-2,mod[p]) % mod[p] * qpow(fac[b][p],mod[p]-2,mod[p]) % mod[p];
}
LL lucas(LL a,LL b,LL p) {
    if(!b) return 1;
    return lucas(a/mod[p],b/mod[p],p) * C(a%mod[p],b%mod[p],p) % mod[p];
}
void solve(int k) {
    for(int i = 1;i < 5;i++) {
        A[i] = (A[i] + lucas(n,k,i)) % mod[i];
    }
}
void exgcd(LL a,LL b,LL &x,LL &y) {
    if(!b) {x = 1;return;}
    exgcd(b,a%b,x,y);
    LL t = x;
    x = y;
    y = t - (a/b) * y;
}
LL crt() {
    LL res = 0;
    for(int i = 1;i < 5;i++) {
        LL x = 0,y = 0;
        LL tmp = (mod[0] - 1) / mod[i];
        y = qpow(tmp,mod[i]-2,mod[i]);
     //   cout << y * A[i] % mod[0] << endl;
        res = (res + 1LL * y * A[i] % (mod[0] - 1) * tmp % (mod[0] - 1)) % (mod[0] - 1);
        // cout << res << endl;
    }
    return (res + mod[0] - 1) % (mod[0] - 1);
}
signed main() {
    // cout << "debug" << endl;
    n = read();g = read();
    for(int x = 1;x < 5;x++)
        {
          fac[1][x]=fac[0][x]=1;
          for(int i=2;i < mod[x];++i)
          fac[i][x] = fac[i-1][x]*i % mod[x];
        }
    if(g % (mod[0]) == 0) {puts("0");return 0;}
    for(int i = 1;i * i <= n;i++) {
        if(n%i) continue;
        solve(i);
        if(n/i != i) solve(n/i); 
    }
    LL ans = crt();
    //cout <<"ans1:: "<< ans << endl;
    ans = qpow(g,ans,mod[0]);
    cout << ans << endl;
//  cout<<1<<endl;
//    system("pause");
    return 0;
}