题目链接：http://poj.org/problem?id=1091
题意：给出一个M,可以从1..M中选出N个数（a,a..a），跳蚤可以左右移动（a,a..a,M）步，问能跳蚤移到左边一格的方案有几种？
思路：假设步数(a,a..a,M)，移动的次数分别为(x,x,..x,x）
1.那么：a*x+a*x+..+a*x+M*x=1 (显然x正负都可以去，左右移动嘛，这里是向左为正)
2.因为M是已给的，求{aa...a}与M最大公约数为1的方案个数， 不如算{a,a..a}中选N个与M最大公约数 不是1
因为我们知道总数为M
而且如果最大公约数不是1，那么最大公约数一定是M质因子中某几个的倍数
即{a1,a2,..an}与M有质约数的情况个数。
3.那么我们只要算出，对于每种M质因子搭配的方案的个数
设y(n)表示 n个M的质因子搭配，即最大公约是 n个M的质因子的积情况个数
用容斥定理得 公约数不为1的个数 f=y(1)-y(2)+y(3)+(-1)t(k)
4.答案就是 M-f
详细过程请看代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e5+10; int prim[maxn],prim_num; void divide(int m)//求出m的质因子 { prim_num=0; for(int i=2;i*i<=m;i++) { if(m%i==0) { prim_num++; prim[prim_num]=i; while(m%i==0) m/=i; } } if(m!=1) { prim_num++; prim[prim_num]=m; } } ll qpow(ll a,ll b)//快速幂 { ll ans=1; while(b) { if(b&1) ans*=a; a=a*a; b>>=1; } return ans; } ll a[maxn],tmp,n,m; void dfs(int b,int ct,int c)//表示从M的质因子中挑选c个,ct表示已选择的个数 { int x; if(ct==c)//已经从中选择了c个质因子 { x=m; for(int i=1;i<=c;i++) x/=a[i]; tmp+=qpow(x,n);//挑完c个后，每个数值都是 a[1]*...*a[c]*k(1<=k<=x),每个数剩下x种选择 return ;//所以总个数是x^n } for(int i=b+1;i<=prim_num;i++) { a[ct+1]=prim[i];//对于第ct+1个选第i个质因子 dfs(i,ct+1,c); } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { ll ans=0; divide(m); for(int i=1;i<=prim_num;i++) { tmp=0; dfs(0,0,i);//N个数都是 M中所有i个质因子选择情况 的倍数的个数 if(i&1)//容斥定理 ans+=tmp; else ans-=tmp; //cout<<i<<" "<<prim[i]<<" "<<ans<<endl; } ans=qpow(m,n)-ans; printf("%lld\n",ans); } return 0; }