题意:
给定整数,计算
思路:
若,则上式为0。否则互质,可以用欧拉降幂:
较大,可以考虑用定理
定理要求模数是质数,尝试分解质因数,发现。
MyCode:
```#include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=2e5+7,mod=999911659; typedef long long int ll; #define eb emplace_back #define ef emplace_front #define ep emplace #define fi first #define se second ll inf[100005]; ll qpow(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1) res=res*a%p; a=a*a%p; b>>=1; } return res; } ll China(int n,ll *m,ll *a,ll M) { ll Mi,x(0); for(int i=0; i<n; i++) { Mi=M/m[i]; x=(x+qpow(Mi,m[i]-2,M)*Mi*a[i])%M; } return (x+M)%M; } ll c(ll n,ll m,ll p) { if(n<m) return 0; return inf[n]*qpow(inf[n-m]*inf[m]%p,p-2,p)%p; } ll lucas(ll n,ll m,ll p) { if (n<m) return 0; if (!n) return 1; return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p; } ll a[4],b[4]= {2,3,4679,35617}; int main() { ios::sync_with_stdio(0); cin.tie(0); ll q,n; cin>>n>>q; if(q%mod==0) return cout<<"0\n",0; inf[0]=inf[1]=1; for(int i=0; i<4; ++i) { for(int j=2; j<=b[i]; ++j) inf[j]=inf[j-1]*j%b[i]; for(ll j=1; j*j<=n; ++j) if(n%j==0){ a[i]=( a[i]+lucas(n,j,b[i]) )%b[i]; if(j*j!=n) a[i]=( a[i]+lucas(n,n/j,b[i]) )%b[i]; } } cout<<qpow(q,China(4,b,a,mod-1),mod)<<'\n'; return 0; }