poj 2478 Farey Sequence（数论：欧拉函数+打表）

本文主要是介绍poj 2478 Farey Sequence（数论：欧拉函数+打表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注意括号内分数分母相同时的区别

f(5)中以5为分母的数其分子均与5互质

进而推得：f(n)中以i为分母的数其各个分子均与i互质

因此:

用筛选法打表phi，再预处理下即可

看到别人说也可以用欧拉函数的积性性质来做，有兴趣的可以看一下

我的代码如下：

#include <stdio.h>
#define MAXN 1001000
#define LL long longLL phi[MAXN];void phi_table(int n) {int i, j;for(i=2; i<=n; ++i) {phi[i] = 0;}phi[1] = 1;for(i=2; i<=n; ++i) {if(!phi[i]) {for(j=i; j<=n; j+=i) {if(!phi[j])phi[j] = j;phi[j] = phi[j]/i*(i-1);}}}for(i=3; i<=n; ++i)phi[i] += phi[i-1];
}int main(void) {int n;phi_table(MAXN);while(scanf("%d", &n), n) {printf("%lld\n", phi[n]);}return 0;
}

这篇关于poj 2478 Farey Sequence（数论：欧拉函数+打表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---