欧拉函数模板

算法模板-数论（欧拉函数） (2010-04-14 13:00:35) 转载 标签： 欧拉函数 it 分类： 算法模板

//欧拉函数计算是少于或等于n的数中与n互质的数的数目 //pku2478 #include #include #include

using namespace std; const int MAXN = 1000001; unsigned int prime[MAXN];//记录素数 unsigned int E[MAXN];//欧拉数组：欧拉数组是少于或等于n的数中与n互质的数的数目 bool visit[MAXN];//标志数组 unsigned long long result[MAXN];

void Eorue() { memset(visit, false, sizeof(visit));

for(int i = 2; i <= MAXN; i++) { if(!visit[i]) { prime[++prime[0]] = i; E[i] = i - 1; } for(int j = 1; j <= prime[0] && prime[j] * i <= MAXN; j++) { visit[prime[j]*i] = true; if(i % prime[j] == 0) { E[i*prime[j]] = E[i] * prime[j]; break; } else E[i*prime[j]] = E[i] * (prime[j] - 1); } } }

void init() { Eorue();

result[1] = 0; for (int i = 2; i <= MAXN; ++i) { result[i] = result[i-1] + E[i]; } }

int main()

欧拉函数求法 1、递推求解

欧拉函数可以很方便的计算小于某个数N但N互质的数的个数, 即M(1<=MM的个数很容易由欧拉函数来计算出来. 欧拉函数的表达式为N*(1-1/f_1)*(1-1/f_2)*(1-1/f_3)....依次类推, 其中f_1, f_2, f_3等是N的不相同的质因子. 例如12=2*2*3那么12有两个不同的质因子2, 3, 由欧拉函数可得小于12但与12互质的个数为12*(1-1/2)(1-1/3)=4, 列举为1, 5, 7, 11. 那么在实际实现欧拉函数的时候, 可以把一个数进行质因子分解, 依次代入欧拉函数进行求解. 我们今天介绍一种用欧拉函数自身的递推关系来实现的方法. 首先介绍这种递推关系, 假设数N有m个不相同的质因子f_1, f_2,f_3....f_m. 那么数(N/f_1)有多少个不同的质因子呢? 分成两种情况来考虑, 1. N只包含一个f_1因子, 那么N/f_1有m-1个因子f_2,f_3,...,f_m. 我们考察N/f_1和N的欧拉函数形式E(N) = N*(1-1/f_1)*(1-1/f_2)*(1-1/f_3)*...*(1-1/f_m) E(N/f_1) = N/f_1*(1-1/f_2)*(1-1/f_3)*...*(1-1/f_m). 把(1-1/f_1)化为(f_1 - 1)/f_1则可以显然看到E(N) = (f_1 - 1)*E(N/f_1). 第二种情况, N包含一个以上的f_1因子, 那么N/f_1包含了与N相同的质因子个数且此时两者的欧拉函数分别记为E(N) = N*(1-1/f_1)*(1-1/f_2)*(1-1/f_3)*...*(1-1/f_m) E(N/f_1) = N/f_1*(1-1/f_1)*(1-1/f_2)*(1-1/f_3)*...*(1-1/f_m). 这个递推关系更明显了E(N) = (f_1)*E(N/f_1). 因此这两种递推关系只与质因子f_1有关, 而f_1可以是N的任意一个质因子. 用代码来实现时可以取N的最小质因子来简化实现过程.

在实际代码过程可以和搜索质数的"筛子法"相结合, 因为"筛子法"相当于优先找到了每个数的最小质因子.

/*==================================================*\ |递推求欧拉函数 phi(i) \*==================================================*/ for (i = 1; i <= maxn; i++) phi[i] = i; for (i = 2; i <= maxn; i += 2) phi[i] /= 2; for (i = 3; i <= maxn; i += 2) if(phi[i] == i) { for (j = i; j <= maxn; j += i) phi[j] = phi[j] / i * (i - 1); } 2单独求法，公式

/*==================================================*\ |单独求欧拉函数 phi(x) \*==================================================*/ unsigned euler(unsigned x) {// 就是公式 unsigned i, res=x; for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++) if(x%i==0) { res = res / i * (i - 1); while (x % i == 0) x /= i; // 保证i一定是素数 } if (x > 1) res = res / x * (x - 1); return res; }

欧拉函数的定义:E(k)=[1,n-1]中与n互质的整数个数).

因为任意正整数都可以唯一表示成如下形式: k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式) 可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1)) =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi); =k*(1-1/p1)*(1-1/p2)....(1-1/pk) ps：在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(a为N的质因素) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;

若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1); http://hi.baidu.com/ldante/blog/item/996b0ea131a7a58f46106443.html 要计算一个正整数n的欧拉函数的方法如下： 下面的程序是求1到10000之间所有整数的欧拉函数 char mark[10000] = {0}; int prime[1230]; int size = 0; int phi[10000];

int main () { int i, j;

/*筛法求素数*/ for (i = 2; i < 10000; i++) { if (!mark[i]) prime[size++] = i;

for (j = 0; j < size && prime[j] * i < 10000; j++) { mark[prime[j] * i] = 1; if (i % prime[j] == 0) break; } } /*求欧拉函数*/ phi[1] = 1; for (i = 2; i < 10000; i++) { if (!mark[i]) { phi[i] = i - 1; continue; } for (j = 0; j < size && prime[j] * prime[j] <= i; j++) { if (i % prime[j] == 0) { if (i / prime[j] % prime[j] == 0) phi[i] = prime[j] * phi[i / prime[j]]; else phi[i] = (prime[j] - 1) * phi[i / prime[j]]; break; } } } return 0; }

从别人那里学到的对求欧拉函数部分的优化，使每个数的欧拉函数只由它的最小素因子求出: phi[1] = 1; for (i = 1; i < 10000; i++) { for (j = 0; j < size && prime[j] * i <= 10000; j++) { if (i % prime[j] == 0) { phi[prime[j] * i] = prime[j] * phi[i]; break; } else { phi[prime[j] * i] = phi[i] * (prime[j] - 1);