Problem

https://www.luogu.org/problemnew/show/P2480

Solution

用 ubuntu 的 factor 命令分解 MOD- 1 得四个质数

然后就可以上 CRT+Lucas 了（雾）

这里主要提醒一点错误：Lucas 是>=不是>！！

Code

// Code by ajcxsu
// Problem: factor

#include<bits/stdc++.h>
#define MOD (999911659ll)
using namespace std;
typedef long long ll;

ll mo [] = {0, 2, 3, 4679, 35617};

ll inv[5][40000];
ll fac[5][40000];

ll lucas(ll n, ll m, int x) {
    if(n<m) return 0;
    if(n>=mo[x] || m>=mo[x]) return 1ll*lucas(n/mo[x], m/mo[x], x)*lucas(n%mo[x], m%mo[x], x)%mo[x];
    return 1ll*fac[x][n]*inv[x][m]*inv[x][n-m]%mo[x];
}

ll qpow(ll x, ll y, ll mo) {
    ll ret=1; x%=mo;
    while(y) {
        if(y&1ll) ret=ret*x%mo;
        x=x*x%mo, y>>=1ll;
    }
    return ret;
}

ll a[5], t[5], M[5];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int u;
    for(int i=1;i<=4;i++) {
        u=mo[i];
        inv[i][0]=inv[i][1]=fac[i][0]=fac[i][1]=1;
        for(int j=2;j<u;j++) inv[i][j]=(-1ll*(u/j)*inv[i][u%j]%u+u)%u;
        for(int j=2;j<u;j++) fac[i][j]=1ll*fac[i][j-1]*j%u, inv[i][j]=1ll*inv[i][j]*inv[i][j-1]%u;
    }

    ll g, n, ans=0;
    cin>>n>>g;
    if(!(g%MOD)) cout<<0<<endl, exit(0);
    for(int i=1;i<=4;i++) {
        for(ll j=1;j*j<=n;j++) 
            if(n%j==0) {
                if(j*j!=n) a[i]=(a[i]+lucas(n, j, i)+lucas(n, n/j, i))%mo[i];
                else a[i]=(a[i]+lucas(n, j, i))%mo[i];
            }
        M[i]=(MOD-1)/mo[i];
        t[i]=qpow(M[i], mo[i]-2, mo[i]);
        (ans+=M[i]*t[i]%(MOD-1)*a[i])%=MOD-1;
    }
    cout<<qpow(g, ans, MOD)<<endl;
    return 0;
}