数论大杂烩，留坑代填，先放代码：
/************************************************************** Problem: 1951 User: JBLee Language: C++ Result: Accepted Time:152 ms Memory:2856 kb ****************************************************************/ #include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+7; const int mod=999911658; int n,g; int sum; int m[5]={0,2,3,4679,35617}; int jc[maxn]; int x,y; int china[maxn]; int ksm(int x,int n,int mo){ int base=1; while(n){ if(n&1) base=base*x%mo; x=x*x%mo; n>>=1; } return base; } int exgcd(int a,int &x,int b,int &y){ if(!b){ x=1;y=0; return a; } int gcd=exgcd(b,x,a%b,y); int tmp=x;x=y;y=tmp-(a/b)*y; return gcd; } int inv(int a,int mo){ exgcd(a,x,mo,y); return (x%mo+mo)%mo; } void work(int p){ jc[0]=1,jc[1]=1; for(int i=2;i<=p;i++) jc[i]=jc[i-1]*i%p; } int comb(int n,int m,int p){ if(m>n) return 0; return jc[n]*inv(jc[n-m],p)%p*inv(jc[m],p)%p; } int lucas(int n,int m,int p){ if(!m) return 1; else return comb(n%p,m%p,p)*lucas(n/p,m/p,p)%p; } int solve(int p){ work(p); int ans=0; for(int i=1;i*i<=n;i++){ if(n%i==0){ ans=(ans+lucas(n,i,p))%p; if(n/i!=i) ans=(ans+lucas(n,n/i,p))%p; } } return ans; } int china_mod(){ for(int i=1;i<=4;i++) china[i]=solve(m[i]); int lcm=1,ans=0,mi; for(int i=1;i<=4;i++) lcm*=m[i]; for(int i=1;i<=4;i++){ mi=lcm/m[i]; exgcd(mi,x,m[i],y); ans=((ans+mi*x*china[i])%lcm+lcm)%lcm; } return ans; } signed main(){ scanf("%lld%lld",&n,&g); if(g%(mod+1)==0){ printf("0 "); return 0; } printf("%lld ",ksm(g,china_mod(),mod+1)); return 0; }