锐客网

  1. 首页 > 睿知 > it技术 > >

POJ2773 Happy 2006容斥原理

IT知识原理容斥容斥原理

于今腐草无萤火，终古垂杨有暮鸦。这篇文章主要讲述POJ2773 Happy 2006容斥原理相关的知识，希望能为你提供帮助。
题目链接：
http://poj.org/problem?id=2773

【POJ2773 Happy 2006容斥原理】

题目大意：
给你两个整数N和K。找到第k个与N互素的数(互素的数从小到大排列)。当中
(1 < = m < = 1000000，1 < = K < = 100000000 )。


解题思路：
K非常大，直接从小到大枚举找出不现实，仅仅能二分答案。二分枚举[1。INF]范围内全部的数x，
找到1~x范围内与N互素的数个数。假设等于K，则就是结果。
然后考虑1~x范围内与N互素的数个数 = x - 1~x范围内与N不互素的数个数
1~x范围内与N不互素的数个数用简单的容斥定理来求就可以。


AC代码：

#include< iostream> #include< algorithm> #include< cstdio> #include< cstring> #include< cmath> #define LL __int64 using namespace std; const LL INF = 0xfffffff0; int Prime[1000010],ct,N; void Divide() { ct = 0; int n = N; for(int i = 2; i < = sqrt(n*1.0); ++i) { if(n % i == 0) { Prime[ct++] = i; while(n % i == 0) n /= i; } } if(n != 1) Prime[ct++] = n; }LL Solve(int n) { LL ans = 0; for(int i = 1; i < (1 < < ct); ++i) { LL odd = 0; LL tmp = 1; for(int j = 0; j < ct; ++j) { if((1 < < j) & i) { odd++; tmp *= Prime[j]; } } if(odd & 1) ans += n/tmp; else ans -= n/tmp; } return n - ans; }int main() { int K; while(~scanf(" %d%d" ,& N,& K)) { Divide(); LL Left = 1, Right = INF, Mid, tmp; while(Left < Right) //二分答案 { Mid = (Left + Right) > > 1; tmp = Solve(Mid); if(tmp > = K) Right = Mid; else Left = Mid + 1; } printf(" %I64d\n" ,Left); }return 0; }











    推荐阅读


    上一篇：解决Android设备不弹出调试授权提醒

    下一篇：AppcanapicloudHBuilder 不同之处解析