/*
古代猪文：Lucas定理+中国剩余定理
999911658=2*3*4679*35617
Lucas定理：(m,n)=(sp,tp)(r,q) %p
中国剩余定理：x=sum{si*Mi*ti}+km
先求出sum{C(d,n)}%p[i]=a[i]
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 999911659
#define maxn 100005
ll m[4]={
2,
3,
4679,
35617};
ll f[4][maxn],a[
4],d[maxn];
ll exgcd(ll a,ll b,ll &x,ll &
y){
if(b==
0){x=
1,y=
0;
return a;}
ll d=exgcd(b,a%
b,x,y);
ll z=x;x=y,y=z-a/b*
y;
return d;
}
ll inv(ll a,ll Mod){
ll x,y;
exgcd(a,Mod,x,y);
return (x+Mod)%
Mod;
}
ll C(int i,ll n,ll k,ll p){
return f[i][n]*inv(f[i][k]*f[i][n-k]%p,p)%
p;}
ll lucas(int i,ll n,ll k,ll p){
int res=
1;
while(n&&
k){
res=res*C(i,n%p,k%p,p)%
p;
if(res==
0)
return 0;
n/=p,k/=
p;
}
return res;
}
ll Pow(ll x,ll n,ll Mod){
ll res=
1;
while(n){
if(n%
2)res=res*x%
Mod;
n>>=
1;x=x*x%
Mod;
}
return res;
}
ll china(int n,ll a[],ll m[]){
ll M=
1,res=
0;
for(
int i=
0;i<n;i++)M*=
m[i];
for(
int i=
0;i<n;i++
){
ll w=M/
m[i],x,y;
exgcd(w,m[i],x,y);
res=(res+x*w*a[i])%
M;
}
return (res+M)%
M;
}
int main(){
ll n,g;
cin>>n>>
g;
if(g==mod){puts(
"0");
return 0;}
int tot=
0;
for(
int i=
1;i*i<=n;i++
)
if(n%i==
0){
//求n的所有质因子
if(i*i==n)d[tot++]=
i;
else d[tot++]=i,d[tot++]=n/
i;
}
for(
int i=
0;i<
4;i++
){
f[i][0]=
1;
for(
int j=
1;j<m[i];j++
)
f[i][j]=f[i][j-
1]*j%
m[i];
}
for(
int i=
0;i<tot;i++
)
for(
int j=
0;j<
4;j++
)
a[j]=(a[j]+lucas(j,n,d[i],m[j]))%
m[j];;
ll ans=china(
4,a,m);
cout<<
Pow(g,ans,mod);
}
转载于:https://www.cnblogs.com/zsben991126/p/10623016.html
