这里先说一下欧拉函数的求法 先说一下筛选素数的方法 void Get_Prime(){ /*筛选素数法*/for(int i = 0; i < N; i++) vis[i] = 1;vis[0] = vis[1] = 0;for(int i = 2; i * i < N; i++)if(vis[i]){for(int j = i * i; j < N; j += i)vis[j] =

http://poj.org/problem?id=2478 求欧拉函数的模板。 初涉欧拉函数，先学一学它基本的性质。 1.欧拉函数是求小于n且和n互质(包括1)的正整数的个数。记为φ(n)。 2.欧拉定理：若a与n互质，那么有a^φ(n) ≡ 1(mod n),经常用于求幂的模。 3.若p是一个质数,那么φ(p) = p-1，注意φ(1) = 1。 4.欧拉函数是积性函数：

题目链接： http://poj.org/problem?id=2478 题目大意： 给你一个数n，对于0 < a < b <= n，求真分数a/b的个数 解题思路： 因为a/b为真分数，所以a和b互质。 求真分数a/b的个数。其实就是求0 < i <= n中，小于i的正整数中， 有多少个与i互质的数。累加起来就是真分数a/b的个数。 其实就是

注意括号内分数分母相同时的区别 f(5)中以5为分母的数其分子均与5互质 进而推得：f(n)中以i为分母的数其各个分子均与i互质 因此: 用筛选法打表phi，再预处理下即可 看到别人说也可以用欧拉函数的积性性质来做，有兴趣的可以看一下 我的代码如下： #include <stdio.h>#define MAXN 1001000#define LL long longLL ph