poj1091跳蚤---------容斥
#include<iostream>#include<cstdlib>#include<stdio.h>#include<math.h>#define ll __int64using namespace std;ll n,m;ll p[65];ll a[65];int cc;ll ans;void get(){ int i; cc=0; ll mm=m; for(i=2;i*i<=mm;i++) { if(mm%i==0) { p[cc++]=i; while(mm%i==0) mm/=i; } } if(mm>1) p[cc++]=mm;}ll quickpower(ll a,ll b){ ll res=1; while(b) { if(b&1) res*=a; a=a*a; b>>=1; } return res;}void get_sum(int id,int step,int num){ if(step==num) { ll uu=m; for(int i=0;i<step;i++) uu/=a[i]; ans+=quickpower(uu,n); return ; } for(int i=id;i<cc;i++) { a[step]=p[i]; get_sum(i+1,step+1,num); } return ;}int main(){ while(scanf("%I64d%I64d",&n,&m)!=EOF) { get(); ll res=quickpower(m,n); for(int i=1;i<=cc;i++) { ans=0; get_sum(0,0,i); if(i&1) res-=ans; else res+=ans; } printf("%I64d\n",res); }}
