古代猪文

数论模板混合好题

#include<bits/stdc++.h>
#define re return
#define ll long long
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>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;
}

#include<bits/stdc++.h>#define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template<typename T>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;}