题目传送门
//容斥定理 #include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long LL; const int maxn=100+5; int fac[maxn],cnt; LL n,m,k,temp; LL pow(LL a,LL b) { LL res=1; while(b) { if(b&1) res=res*a; b>>=1; a=a*a; } return res; } int a[maxn]; void dfs(int b,int x,int pos) { if(x==pos) { LL x1=1,x2; for(int i=1;i<=pos;i++) x1*=a[i]; //cout<<x1<<endl; x2=k/x1; temp+=pow(x2,n); return; } for(int i=b;i<cnt;i++) { a[x+1]=fac[i]; dfs(i+1,x+1,pos); } } int main() { while(scanf("%lld%lld",&n,&m)==2) { cnt=0; k=m; for(int i=2;1l*i*i<=m;i++) { if(m==1) break; if(m%i==0) { fac[cnt++]=i; while(m%i==0) m/=i; } } if(m!=1) { fac[cnt++]=m; } //for(int i=0;i<cnt;i++) // cout<<fac[i]<<endl; //cout<<cnt<<endl; LL sum=pow(k,n),ans=0; //容斥定理，寻找原问题的逆问题 for(int i=1;i<=cnt;i++) { temp=0; dfs(0,0,i); if(i&1) ans+=temp; else ans-=temp; } sum-=ans; printf("%lld\n",sum); } }
