本文主要是介绍poj 2773 Happy 2006(数论：欧拉函数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出n, k，输出与n互质的第k个正整数
这个题归根结底用到了一个性质：
gcd(a, b) == gcd(a, b+a*t) (t=0,1,2...)
所以一种方法就是找到小于n且与n互质的所有数prime[]以及其个数cnt
如果k<tot，则直接输出
否则根据上式可知存在循环节，相邻两个循环节之间相差：k/cnt*m
所以结果应该为：k/cnt*m+prime[k%(cnt-1)]
但是还要考虑一种情况k%cnt == 0
此时结果应该为：（k/cnt-1）*m+prime[cnt-1];
暴力求素数2407打表代码如下：
#include <cstdio>
#include <iostream>
#define MAXN 1001000
using namespace std;int prime[MAXN];int gcd(int a, int b) {return b ? gcd(b, a%b) : a;
}int main(void) {int m, k, i, cnt;while(scanf("%d%d", &m, &k) != EOF) {cnt = 0;for(i=1; i<=m; ++i)if(gcd(m, i) == 1)prime[cnt++] = i;if(k % cnt)cout << k/cnt*m+prime[k%cnt-1] << endl;else cout << (k/cnt-1)*m+prime[cnt-1] << endl;}return 0;
}而上面用到了求n以内与n互质的数以及个数
所以很容易想到用欧拉函数
这个题用欧拉函数要快的多得多
16ms代码如下：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 1001000
using namespace std;int prime[MAXN];
bool vis[MAXN];int euler_phi(int n) {int m, cnt, ans, tmp;m = sqrt(n+0.5);cnt = 0;ans = tmp = n;for(int i=2; i<=m; ++i) {if(n%i == 0) {prime[cnt++] = i;ans = ans/i*(i-1);n /= i;while(n%i == 0)n /= i;for(int j=i; j<=tmp; j+=i)vis[j] = true;}}if(n > 1) {ans = ans/n*(n-1);for(int j=n; j<=tmp; j+=n)vis[j] = true;} return ans;
}int get(int n) {int cnt = 0;for(int i=1; i<MAXN; ++i) {if(!vis[i])++cnt;if(cnt == n)return i;}
}int main(void) {int m, k;while(scanf("%d%d", &m, &k) != EOF) {if(m==1) {printf("%d\n", k);continue;}memset(vis, 0, sizeof(vis));int ans = euler_phi(m);int n = (k-1)%ans+1;printf("%d\n", (k-1)/ans*m+get(n));}return 0;
}这篇关于poj 2773 Happy 2006(数论：欧拉函数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
