首页 > 代码库 > 【poj1091】 跳蚤
【poj1091】 跳蚤
http://poj.org/problem?id=1091 (题目链接)
题意
给出一张卡片，上面有n+1个数，其中最大的数为m，每次可以向前或者向后走卡片上面的步数。问有多少种方案选出n个数，使得存在一种走的方案经过若干步后可以达到与起点距离为1的位置上。
Solution
今天考试题，又是一道大原题。。。
我们假设卡片上的数分别为：{a1,a2,a3,a4······an,m}，那么如果要满足题目要求，就是说存在一个数列x:{x1,x2,x3,x4······xn,xn+1}使得a1x1+a2x2+a3x3+a4x4+······anxn+mxn+1=1。也就是说gcd(a1x1,a2x2,a3x3,a4x4,······anxn,mxn+1)=1（欧几里得）。
所以我们知道了合法的卡片上面的数的gcd一定为1，但是这样的话并不是特别好处理，我们考虑求出不合法的卡片方案数，再用总的卡片方案数减去不合法的得到答案。
不合法的方案就是卡片上的数字的gcd不为1，于是我们可以枚举它的gcd。对于1个gcd：x，它的方案数为：pow(m/x,n)。这个式子的意思就是在小于等于m的数中有m/x个能被x整除的数，于是卡片上的每一个数就有m/x种选法。这就转化为了容斥原理的经典问题：求小于等于m的数中，能够整除m的数的个数。我们只是将统计答案那一步稍加修改一下罢了。注意，如果统计过gcd为x的情况，那么不用再统计gcd为x2的情况了。
综上所述，我们先将m质因数分解，然后容斥统计即可。
其实这道题还有个隐藏数据范围：mn≤1016，是不是很高兴，不用写高精度了。
代码
// poj1091#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL n,m,ans,p[1000];int num;void divide(LL m) { num=0; for (int i=2;i*i<=m;i++) if (m%i==0) { p[++num]=i;m/=i; while (m%i==0) m/=i; } if (m>1) p[++num]=m;}LL power(LL a,LL b) { LL res=1; while (b) { if (b&1) res*=a; a*=a; b>>=1; } return res;}void dfs(int x,int y,int z) { if (z>m) return; if (x==num+1) { if (y) { if (y&1) ans-=power(m/z,n); else ans+=power(m/z,n); } return; } dfs(x+1,y,z); dfs(x+1,y+1,z*p[x]);}int main() { scanf("%lld%lld",&n,&m); ans=power(m,n); divide(m); dfs(1,0,1); printf("%lld",ans); return 0;}
【poj1091】 跳蚤
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。