卢卡斯定理
注意特判底数和模数相等的情况
#include#include #include #include #include #define ll long longusing namespace std;const int MOD = 999911659;ll n, g, p[5] = {0, 2, 3, 4679, 35617}, ans[5], fac[100000], ni[100000];ll exgcd(ll a, ll b, ll & x, ll & y ){ if(!b) { x = 1; y = 0; return a; } ll t = exgcd(b, a % b, y, x); y -= a / b * x; return t;}ll getni(ll x, ll p) { ll a, b; exgcd(x, p, a, b); (a += p) %= p; return a;} ll lucas(ll a, ll b, ll p) { if(a < b) return 0; if(a < p) return fac[a] * ni[b] * ni[a - b] % p; else return lucas(a % p, b % p, p) * lucas(a / p, b / p, p) % p;}void work(int x) { memset(fac, 0, sizeof(fac)); memset(ni, 0, sizeof(ni)); fac[1] = fac[0] = ni[0] = ni[1] = 1; for(int i = 2; i < p[x]; i++) fac[i] = fac[i - 1] * i % p[x]; for(int i = 2; i < p[x]; i++) ni[i] = (p[x] - p[x] / i) * ni[p[x] % i] % p[x]; for(int i = 2; i < p[x]; i++) (ni[i] *= ni[i - 1]) %= p[x]; ll i = 1ll; for( ; i * i < n; i++) { if(n % i == 0) { ans[x] += lucas(n, i, p[x]); //cout << ans[x] << endl; ans[x] += lucas(n, n / i, p[x]); //cout << ans[x] << endl; ans[x] %= p[x]; //cout << ans[x] << endl; } } if(i * i == n) ans[x] += lucas(n, i, p[x]); //cout << ans[x] << endl; //cout << endl; ans[x] %= p[x];}ll CRT() { ll M = MOD - 1; ll rt = 0ll; for(int i = 1; i <= 4; i++) { rt += ans[i] * getni(M / p[i], p[i]) * (M / p[i]) % M; } //cout << rt << endl; return rt % M;}ll quick_mod(ll a, ll k) { ll ans = 1ll; while(k) { if(k & 1ll) (ans *= a) %= MOD; (a *= a) %= MOD; k >>= 1; } return ans;}int main() { cin >> n >> g; if(g == MOD) {printf("0\n");return 0;} for(int i = 1; i <= 4; i++) { work(i); //cout << ans[i] << endl; } cout << quick_mod(g, CRT()) << endl; return 0;}