首页 > 代码库 > poj 2773 Happy 2006(欧拉函数应用)
poj 2773 Happy 2006(欧拉函数应用)
http://poj.org/problem?id=2773
题意:输入n,k,求与n不互素的第k个数,k可能大于n。
思路:以n=6为例,与6互素的数有一定规律。{1,5},{7,12},{13,18}......,发现在[1,n],[n+1,n*2]......[m*n+1,(m+1)*n]区间内素数个数相同,且对应位置的数都相差n的整数倍。因此只要求出[1,n]内的与n互素的数即可。这个过程没必要一个一个枚举,可以用欧拉函数解决。因为欧拉函数已经求出了n的所有质因子,与n不互素的数都与n有相同的质因子公约数,可以用这些质因子的整数倍去标记与n不互素的数。然后在线性时间内的求第k个与n互素的数。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int maxn = 1000010; int n,k,kk; int flag[maxn]; //求Eular(n),同时求出n的质因子,用这些质因子标记与n不互素的数。 int Eular(int n) { int ret = n,m = n; memset(flag,0,sizeof(flag)); for(int i = 2; i*i <= n; i++) { if(n%i == 0) { for(int j = 1; j*i <= m; j++) flag[j*i] = 1; ret -= ret/i; while(n%i == 0) n /= i; } } if(n > 1) { for(int j = 1; j*n <= m; j++) flag[j*n] = 1; ret -= ret/n; } return ret; } int main() { while(~scanf("%d %d",&n,&k)) { int cnt = Eular(n),t; t = k/cnt; if(k%cnt == 0) t--; kk = k - t*cnt; int cou = 0,i; for(i = 1; i <= n; i++) { if(flag[i] == 0) cou++; if(cou == kk) break; } printf("%d\n",i+t*n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。