Euler

发表于 | 评论数： | 阅读次数： | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 4 分钟

Euler

定义

欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。

计算

φ函数的值：

φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n))

其中p(1),p(2)…p(n)为x的所有质因数;x是正整数;

φ(1)=1(唯一和1互质的数，且小于等于1)。

注意：每种质因数只有一个。

例如:

​ φ(10)=10×(1-1/2)×(1-1/5)=4;

​ 1 3 7 9

​ φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

​ φ(49)=49×(1-1/7)=42;

性质

1.对于质数p，φ(p)=p−1。

2.若p为质数，$n=p^{k}$ ,则 φ(n)=$p^{k}-p^{k-1}$

3.欧拉函数是积性函数，但不是完全积性函数。若m,n互质，则φ(m∗n)=φ(m)∗φ(n) 。特殊的，当m=2，n为奇数时，φ(2*n)=φ(n)。

4.当n>2时，φ(n)是偶数。

5.小于n的数中，与n互质的数的总和为：φ(n) * n / 2 (n>1)。

6.n=$\sum_{d|n}{φ(d)}$ ，即n的因数（包括1和它自己）的欧拉函数之和等于n

7.欧拉降幂公式：$A^{B} mod C = A^{B mod φ(C) + φ(C) } mod C$

板子

求解欧拉函数值才是关键。

暴力

复杂度 O(sqrt(n))

φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 

1
2
3
4
5
6
7
8
9
10
11
ll Euler(ll n){ //返回Euler(n)   
     ll res=n,a=n;  
     for(int i=2;i*i<=a;i++){  
         if(a%i==0){  
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出   
             while(a%i==0) a/=i;  
         }  
     }  
     if(a>1) res=res/a*(a-1);  
     return res;  
}

埃拉托斯特尼筛求欧拉函数

复杂度 O(n*log(log(n)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void euler(int n)
{
    for (int i=1;i<=n;i++) phi[i]=i;
    for (int i=2;i<=n;i++)
    {
        if (phi[i]==i)//这代表i是质数
        {
            for (int j=i;j<=n;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
            }
        }
    }
}

欧拉筛求欧拉函数

复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int prime[N],phi[N],num;
void Euler(int n)
{
	phi[1]=1;//1要特判 
	for (int i=2;i<=n;i++)
	{
		if (flag[i]==0)//这代表i是质数 
		{
			prime[++num]=i;
			phi[i]=i-1;
		}
		for (int j=1;j<=num&&prime[j]*i<=n;j++)//经典的欧拉筛写法 
		{
			flag[i*prime[j]]=1;//先把这个合数标记掉 
			if (i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];//若prime[j]是i的质因子，则根据计算公式，i已经包括i*prime[j]的所有质因子 
				break;//经典欧拉筛的核心语句，这样能保证每个数只会被自己最小的因子筛掉一次 
			}
			else phi[i*prime[j]]=phi[i]*phi[prime[j]];//利用了欧拉函数是个积性函数的性质 
		}
	}
}