首页 > 代码库 > 【poj2773】 Happy 2006
【poj2773】 Happy 2006
http://poj.org/problem?id=2773 (题目链接)
题意：给出两个数m,k，要求求出从1开始与m互质的第k个数。
Solution
数据范围很大，直接模拟显然是不行的，我们需要用到一些奇奇怪怪的方法。
考虑是否可以通过某些途径快速得到解，然而并没有头绪。正难则反，能不能通过计算不与m互质的数的个数来得到互质的数的个数呢？答案是可行的，我们可以运用容斥。
二分一个答案mid，容斥统计出在区间[1，mid]中是m的质因子的倍数的数的个数ans，然后我们可以用mid-ans得到区间中有多少个与m互质的数，不断二分下去，直到得出答案。
容斥统计的经典应用。
代码：
// poj2773#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1ll<<62);#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int n,cnt,p[500],a[200],vis[2010];LL ans,m,k,mid;LL gcd(LL a,LL b) { return a%b==0 ? b : gcd(b,a%b);}void dfs(int x,int y,int z) { if (x==n+1) { if (y>0) { if (y&1) ans+=mid/z; else ans-=mid/z; } return; } dfs(x+1,y,z); LL tmp=a[x]/gcd(z,a[x]); if ((double)tmp*z<=mid) dfs(x+1,y+1,z*tmp);}int main() { for (int i=2;i<=2000;i++) if (!vis[i]) { for (int j=i+i;j<=2000;j+=i) vis[j]=1; p[++cnt]=i; } while (scanf("%lld%lld",&m,&k)!=EOF) { memset(a,0,sizeof(a));n=0; for (int i=1;i<=cnt;i++) if (m%p[i]==0) { while (m%p[i]==0 && m>1) m/=p[i]; a[++n]=p[i]; } if (m>1) a[++n]=m; sort(a+1,a+1+n); LL L=1,R=inf; while (L<R) { mid=(L+R)>>1; ans=0;dfs(1,0,1); if (mid-ans>=k) R=mid; else L=mid+1; } printf("%lld\n",L); } return 0;}
【poj2773】 Happy 2006
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。