数论模板混合好题

#include
     
      #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=36000;ll jc[maxn],inv[maxn],jcinv[maxn],N,G;ll C(int n,int m,int mod)//组合数 {    if(m>n)re 0;    re jc[n]*jcinv[n-m]%mod*jcinv[m]%mod;}ll LUCAS(int n,int m,int mod)//卢卡斯定理 {    if(!m)re 1;    re C(n%mod,m%mod,mod)*LUCAS(n/mod,m/mod,mod)%mod;}inline void Get_math(int mod){    //得到当前模数下的阶乘，阶乘逆元     jcinv[0]=jcinv[1]=inv[1]=jc[1]=jc[0]=1;    inc(i,2,mod)    {        inv[i]=(mod-mod/i)*inv[mod%i]%mod;        jcinv[i]=jcinv[i-1]*inv[i]%mod;        jc[i]=jc[i-1]*i%mod;    }}inline ll Get_crt(int mod){        ll sum=0;    Get_math(mod);    inc(i,1,sqrt(N))    if(N%i==0)//寻找整除N的K     {        sum=(sum+LUCAS(N,i,mod))%mod;        if(i*i!=N)//防止重复         sum=(sum+LUCAS(N,N/i,mod))%mod;    }    re sum;}inline ll pow(ll a,ll x,ll mod){    if(!a)re 0;    ll ret=1;    while(x)    {        if(x&1)ret=ret*a%mod;        a=a*a%mod;        x>>=1;    }    re ret;}int main(){    freopen("in.txt","r",stdin);    ll a1,a2,a3,a4,x,M=999911658;    ll inv1,inv2,inv3,inv4;    rd(N),rd(G);            //得到中国剩余定理的X=(请当做同余)A(mod p)中的A     a1=Get_crt(2);     a2=Get_crt(3);    a3=Get_crt(4679);    a4=Get_crt(35617);    //剩余定理求解     inv1=pow(M/2,2-1,M)*a1;    //Mi*(Mi^(p-2))*ai前面可以合并    //并对M取模得到最小正整数解     inv2=pow(M/3,3-1,M)*a2;    inv3=pow(M/4679,4679-1,M)*a3;    inv4=pow(M/35617,35617-1,M)*a4;         printf("%lld",pow(G%(M+1),(inv1+inv2+inv3+inv4)%M,M+1));    re 0;}