【容斥原理】【分解质因数】poj1091 跳蚤
题意转化为求一个线性组合a1*x1+a2*x2+...+an*xn+m*xn+1=1在什么时候可以有解。(ai在1~m的范围内任取)
易得当且仅当gcd(a1,a2,...,an)=1时可能有解。
然后我们转化为求补集。即答案为m^n-（每个ai中都含有m的质因子的方案数）。
可以通过容斥原理实现。
#include<cstdio>
using namespace std;
typedef long long ll;
int n,m;
int zyz[33],K;
ll ans;
ll Pow(ll x,int p){
ll res=1;
for(;p;--p){
res*=x;
}
return res;
}
void dfs(int cur,int now,int dep){
if(dep){
ans+=(((dep&1) ? 1ll : -1ll)*Pow(now,n));
}
for(int i=cur+1;i<=K;++i){
dfs(i,now/zyz[i],dep+1);
}
}
int main(){
scanf("%d%d",&n,&m);
int mm=m;
for(int i=2;i*i<=m;++i){
if(mm%i==0){
zyz[++K]=i;
while(mm%i==0){
mm/=i;
}
}
}
if(mm>1){
zyz[++K]=mm;
}
dfs(0,m,0);
printf("%lld
",Pow(m,n)-ans);
return 0;
}