P2480 0pts求助

#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ll pr[15],ys[1010],md[15];
ll n,g;
inline ll ksm(ll a,ll b,ll p){
	ll ans = 1;
	while (b){
		if (b & 1)
			ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
inline ll Inv(ll a,ll p){
	return ksm(a,p - 2,p);
}
ll jc[35990];
inline void init(ll p){
	jc[0] = 1;
	for (int i = 1;i <= 35888;i ++){
		jc[i] = jc[i - 1] * i % p;
	}
}
inline ll Lucas(ll a,ll b,ll p){
	if (a == b || b == 0) return 1;
	if (a < b) return 0;
	if (a > p || b > p) return Lucas(a % p,b % p,p) * Lucas(a / p,b / p,p) % p;
	else return jc[a] * Inv(jc[a - b],p) % p * Inv(jc[b],p) % p;
}
int main(){
	cin >> n >> g;
	ll y = 999911658,cnt = 0,cnt2 = 0;
	for (int i = 2;i * i <= y;i ++){
		while (y % i == 0){
			y /= i;
			pr[++cnt] = i;
		}
	} 
	if (y) pr[++cnt] = y;
	for (int i = 2;i * i < n;i ++){
		if (n % i == 0){
			ys[++cnt2] = i;
			ys[++cnt2] = n / i;
		}
	}
	if ((ll)sqrt(n) * (ll)sqrt(n) == n) ys[++cnt2] = (ll)sqrt(n);
	for (int i = 1;i <= cnt;i ++){
		init(pr[i]);
		for (int j = 1;j <= cnt2;j ++){
			md[i] += Lucas(n,ys[j],pr[i]);
			md[i] %= pr[i];
		}
	}
	ll ans = 0;
	for (int i = 1;i <= cnt;i ++){
		ll mi = 999911658 / pr[i];
		ll ci = mi * Inv(mi,pr[i]);
		ans += ci * md[i];
		ans %= 999911659;
	}
	cout << ans << endl;
	cout << ksm(g,ans,999911659) << endl;
	return 0;
}