求助

#include<bits/stdc++.h>

using namespace std;

const int N=50010;

#define ll long long 

ll n,g,p=999911659,a[5],b[5]={0,2,3,4679,35617},jc[N],t[5],sum;

ll quickmi(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;
}

void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0) {
		x=1;y=0;return;
	}
	exgcd(b,a%b,x,y);
	ll z=x;x=y;y=z-(a/b)*y;
	return;
}

ll C(ll n,ll m,ll p)
{
	if(n<m) return 0;
	return jc[n]*quickmi(jc[m],p-2,p)%p*quickmi(jc[n-m],p-2,p)%p;
}

ll lucas(ll n,ll m,ll p)
{
	if(n<m) return 0;
	if(!n) return 1;
	return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p; 
}

int main()
{
	cin>>n>>g;
	if(g%p==0) {
		cout<<"0";
		return 0;
	}
	for(ll i=1;i<=4;i++){
		jc[0]=1;
		for(ll j=1;j<=b[i];j++)
			jc[j]=(jc[j-1]*j)%b[i];
		for(ll j=1;j*j<=n;j++){
			if(n%j!=0) continue;
			a[i]=(a[i]+lucas(n,j,b[i]))%b[i];
			if(n%j!=j) a[i]=(a[i]+lucas(n,n/j,b[i]))%b[i];
			
		}	
		sum=(sum+a[i]*((p-1)/b[i])%(p-1)*quickmi((p-1)/b[i],b[i]-2,b[i]))%(p-1);

	}
	cout<<quickmi(g,sum,p);
	return 0;
}

AC记录