欧拉定理不要忘记!!

#include <bits/stdc++.h>
#define N 100000
#define ll long long
#define ull unsigned long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int array[10]={2,3,4679,35617};
ll mult(ll x,ll y,ll mod)
{
ll tmp=(long double)x/mod*y;
return ((ull)x*y-tmp*mod+mod)%mod;
}
ll qpow(ll base,ll k,ll mod)
{
ll tmp=1;
for(;k;k>>=1,base=mult(base,base,mod)) if(k&1) tmp=mult(tmp,base,mod);
return tmp;
}
struct Lucas
{
int mod;
int fac[N];
ll inv(ll x)
{
return qpow(fac[x],mod-2,mod);
}
void init(int p)
{
mod=p;
fac[0]=1;
for(int i=1;i<=mod;++i) fac[i]=(ll)fac[i-1]*i%mod; // inv[i]=qpow(fac[i],mod-2,mod);
}
ll C(int n,int m)
{
if(m==0) return 1;
if(n<m) return 0;
return (ll)(1ll*fac[n]*inv(m)%mod*inv(n-m)%mod)%mod;
}
ll solve(int n,int m)
{
if(m==0) return 1;
return (solve(n/mod,m/mod)*C(n%mod,m%mod))%mod;
}
}comb;
struct CRT
{
int n;
ll arr[N],brr[N];
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll gcd=exgcd(b,a%b,x,y),tmp=x;
x=y,y=tmp-a/b*y;
return gcd;
}
ll ExCRT()
{
ll ans=arr[1],M=brr[1];
for(int i=2;i<=n;++i)
{
ll a=M,b=brr[i],c=arr[i]-ans,gcd,x,y;
gcd=exgcd(a,b,x,y),b=abs(b/gcd);
x=x*(c/gcd),x=(x%b+b)%b;
ans+=M*x;
M*=brr[i]/__gcd(brr[i],M);
ans=(ans%M+M)%M;
}
return ans;
}
}crt;
int main()
{
// setIO("input");
int i,j;
ll nn,gg,re,tmp,h;
scanf("%lld%lld",&nn,&gg);
if(gg%(999911659)==0)
{
printf("0\n");
return 0;
}
for(i=0;i<4;++i)
{
comb.init(array[i]),re=0,h=nn;
for(j=1;j*j<nn;++j)
{
if(nn%j==0)
{
re=(re+comb.solve((int)nn,j))%array[i];
re=(re+comb.solve((int)nn,nn/j))%array[i];
}
}
if(j*j==nn) re=(re+comb.solve((int)nn,j))%array[i];
crt.arr[i+1]=re;
crt.brr[i+1]=(ll)array[i];
}
crt.n=4;
tmp=crt.ExCRT();
printf("%lld\n",qpow(gg,tmp,999911659));
return 0;
}

  

05-08 07:55
查看更多