点开POJ，看到一道中文题，就点开看了看，发现这题我好像不会

参考了这篇博客：

对于跳蚤来说，需要选出一组整数x1,x2,x3......xn满足a1*x1+a2*x2+a3*x3+...+an*xn=1，其中an=m

而这个方程有解的充要条件就是a1,a2,a3......an互质

正难则反，我们考虑有多少是不满足互质的，将m质因数分解，枚举素因子，利用容斥完成这道题

（之前也不会这种容斥的写法，想了想觉得很有道理）

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=200;int n,m;int p[N],tot,d[N];ll ans;ll qpow(ll x,ll y){  ll ret=1;  while(y)    {      if(y&1) ret=ret*x;      x=x*x;      y>>=1;    }  return ret;}void div(int x){  /*  int t=2;  while(x!=1)    {      if(x%t==0) p[++tot]=t;      while(x%t==0) x/=t;      t++;    }*/  // for(int i=1;i<=tot;i++) printf("%d%c",p[i],"*\n"[i==tot]);  for(int i=2;i*i<=x;i++)    {      if(x%i==0)p[++tot]=i,x/=i;      while(x%i==0) x/=i;    }  if(x>1) p[++tot]=x;}ll qaq;void dfs(int st,int dep,int up){  if(dep==up+1)    {      int x=m;      for(int i=1;i<=up;i++) x/=d[i];      qaq+=qpow(x,n);      return ;    }  for(int i=st;i<=tot;i++)    {      d[dep]=p[i];      dfs(i+1,dep+1,up);    }}int main(){  while(~scanf("%d%d",&n,&m))    {      tot=0;ans=0;      div(m);      for(int i=1;i<=tot;i++)    {      qaq=0;      dfs(1,1,i);      if(i&1) ans+=qaq;      else ans-=qaq;    }      printf("%lld\n",qpow(m,n)-ans);    }  return 0;}