POJ-1091-跳蚤
题意简化之后就是给你一个数m，一个数n，让你构造一个长度为n+1的序列，第n+1个数为m，保证这n+1个数<=m,而且这n+1个数的最大公约数为1。
我们无法直接计算最大公约数为1的组合数，所以我们只要计算出所有最大公约数不为1的再用总排列数减去即可，最大公约数不为1的时候只能为m的因子，所以我们只要对m的质因子容斥一下，求一下每种质因子的组合作为最大公约数的情况就可以了。
容斥定理第八题代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll pow_(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a;a=a*a;b>>=1;}return ans;
}
vector<int> v;
int main()
{ll n,m;scanf("%lld%lld",&n,&m);ll ans=pow_(m,n);ll ans2=0;ll tmp=m;for(ll i=2;i*i<=m;i++){if(m%i==0){v.push_back(i);while(m%i==0) m/=i;}}if(m>1) v.push_back(m);for(int i=1;i<(1<<v.size());i++){ll num=1;int cnt=0;for(int j=0;j<v.size();j++){if(i&(1<<j)){cnt++;num=num*v[j];}}if(cnt&1){ans2+=pow_(tmp/num,n);}else{ans2-=pow_(tmp/num,n);}}ans=ans-ans2;printf("%lld\n",ans);return 0;
}