【欧拉函数-入门】

基本定义

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目(（φ(1)=1）)。此函数以其首名研究者欧拉命名((Euler's totient function))，它又称为(Euler's totient function)、(φ)函数、欧拉商数等。 例如(φ(8)=4)，因为(1,3,5,7)均和(8)互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

欧拉函数

说一下，上面说这么多，就只有第一句有用
欧拉函数，就是求比n小的数中和n互质的数的个数。
来几条很基本的性质：
1.对于任何一个质数(p)，(varphi(p)=p-1)（对于质数来说，比它小的数都与它互质）
2.若(p)为质数，(n=p^k)，那么(varphi(n)=p^k-p^{k-1})
3.欧拉函数是积性函数，(varphi (n imes m)=varphi (n) imes varphi (m))

欧拉函数值求法

首先贴公式
(φ(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)。注意：每种质因数只有一个。

---

以下是求法
和这篇讲乘法逆元的博客类似地，我们还是分两种情况来考虑如何求值。

一、单个求值

对于求单个数的欧拉函数值，我们可以用这样的方法：

int phi(int n)
{
    int ans=n;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
		{
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

这种方法的实质就是直接求小于或等于n,且与n互质的个数。时间复杂度(O(sqrt n))

二、求区间内的欧拉函数值

分两种方法，重点讲第二种。
第一种，欧拉筛预处理所有范围的素数，然后递推跑一遍顺便存入数组方便后续累加。
第二种，直接递推，打入数组，当然和第一种一样，可以用前缀和优化，直接(O(1))输出。
先贴递推代码：

int phi[3000010];
void euler_table()
{
	int n=3000005;
    phi[1]=1;
    for(int i=1;i<=n;i++)
    	phi[i]=i;
    for(int i=2;i<=n;i++)
        if(phi[i]==i)
            for(int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i-1);
    return;
}

和上面的方法有点类似，但是需要多几个判断+存进数组。维护前缀和就初始化完了再遍历一遍就可以了...
ov.
摸鱼酱.