首页 > 代码库 > 欧拉函数相关的题目
欧拉函数相关的题目
POJ 1284
求原根个数：
即求 euler(euler(p)) = euler(p-1) 其中p为奇素数
又有 euler(x) = x*(1-1/p1)*...*(1-1/pk) 其中pk为x的质因数
#include <cstdio>#include <cstring>int all, p, ans, num[100000];bool pd[100000];int main(){ pd[1] = 1; for(int i = 1; i < 100000; i++) if(!pd[i]) { num[all++] = i; for(int j = i+i; j < 100000; j += i) pd[j] = 1; } while(scanf("%d", &p) != EOF) { ans = --p; for(int i = 0; i < all && num[i] <= p; i ++) if(p%num[i] == 0) ans = ans/num[i]*(num[i]-1); printf("%d\n", ans); } return 0;}
POJ 2407
求与n互质的个数：
即求euler(n)
#include <cstdio>#include <cstring>int all, num[100000], ans, n;bool pd[100000];int main(){ pd[1] = 1; for(int i = 1; i <= 100000; i++) if(!pd[i]) { num[all++] = i; for(int j = i+i; j <= 100000; j += i) pd[j] = 1; } while(scanf("%d", &n) != EOF) { if(n == 0) break; ans = n; for(int i = 0; i < all && num[i] <= n; i ++) if(n%num[i] == 0) { ans = ans/num[i]*(num[i]-1); while(n%num[i] == 0) n /= num[i]; } if(n != 1) ans = ans/n*(n-1); printf("%d\n", ans); } return 0;}
POJ 2478
求解前n项欧拉函数之和
看到网上一个比较漂亮的求解欧拉函数的方法。
整个求法其实类似筛法求素数。
对于任何数 x = 2^k * p 其中p为奇数，以下用phi即那个希腊字符表示欧拉函数
故 对于k>0 phi[x] = 2^k * ( 1 - 1/2) * phi[p] = 2^(k-1) * phi[p] = 2^(k-1) * p * (1-1/p1) * ... * (1- 1/pn) = x/2 * (1-1/p1) * ... * (1- 1/pn) 其中p1 .. pn 为p的质因子。 故每次筛法求出素数时可以向上进行求解欧拉函数。
对于k=0 phi[x] = x * (1-1/p1) * ... * (1- 1/pn)
故有此算法
可以大致看出 复杂度不差于O(nlgn)
#include <cstdio>#include <cstring>#define MAXN 1000005int phi[MAXN], n;long long sum[MAXN];void get_phi(){ phi[1] = 0; for(int i = 2; i < MAXN; i++) if(i&1) phi[i] = i; else phi[i] = i/2; for(int i = 2; i < MAXN; i++) if(phi[i] == i) // i为素数 for(int j = i; j < MAXN; j += i) phi[j] = phi[j]/i*(i-1);}int main(){ get_phi(); for(int i = 1; i < MAXN; i ++) sum[i] = sum[i-1]+phi[i]; while(scanf("%d", &n) != EOF && n) printf("%lld\n", sum[n]); return 0;}
欧拉函数相关的题目
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。