题目链接: http://poj.org/problem?id=1091
题意: 给出一个 M, 可以从 1..M 中选出 N 个数 (a1,a2..an), 跳蚤可以左右移动(a1,a2..an,M) 步, 问能跳蚤移到左边一格的方案有几种?
思路: 假设步数(a1,a2..an,M), 移动的次数分别为(x1,x2,..xn,xn+1)
1. 那么: a1*x1+a2*x2+..+an*xn+M*xn+1=1 (显然 xi 正负都可以去, 左右移动嘛, 这里是向左为正)
2. 因为 M 是已给的, 求 {a1,a2...an} 与 M 最大公约数为 1 的方案个数, 不如算 {a1,a2..an} 中选 N 个与 M 最大公约数 不是 1
因为我们知道总数为 MN
而且如果最大公约数不是 1, 那么最大公约数一定是 M 质因子中某几个的倍数
即 {a1,a2,..an} 与 M 有质约数的情况个数.
3. 那么我们只要算出, 对于每种 M 质因子搭配的方案的个数
设 y(n)表示 n 个 M 的质因子搭配, 即最大公约是 n 个 M 的质因子的积情况个数
用容斥定理得 公约数不为 1 的个数 f=y(1)-y(2)+y(3)+(-1)k-1t(k)
4. 答案就是 MN-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;
- }
poj 1091 跳蚤(容斥定理 + 质因子分解)
来源: http://www.bubuko.com/infodetail-3257462.html