浅谈欧拉函数
本篇博客简单讲解一下欧拉函数的相关知识点。欧拉函数属于信息学奥林匹克竞赛知识点中数论方面的内容，是数学的一个分支。理解好欧拉函数对开发思维（emm瑟瑟发抖）有很大的帮助。
欧拉函数的概念
欧拉函数的定义是：对于一个正整数(n)，它的欧拉函数是所有小于等于(n)的正整数中所有与(n)互质的数的数目。记作(Phi (n))
例：
(Phi (8)=4)（(1,3,5,7)与(8)均互质）
欧拉函数的基本性质
欧拉函数的基本性质有三（最基本的）：
第一个很简单我就不说了。
第二个，因为(p)为质数，所以很显然，从(1-(p-1))的所有数都与其互质，但是因为欧拉函数的定义是小于等于(p)的所有数，所以(p)自己是不满足条件的。那么就得证了。
第三个，这是个比较常用的条件。证明也比较好理解，我们可以画一个数轴（在这里我就不画了）。因为(p)是个质数，所以在整个的(p^m)个数中，只有(p)的倍数是与之不互质的，其他的数都与其互质。那么根据容斥原理（这个原理只要学完高中数学必修一集合那部分的都应该会），这个(Phi (p^m))就应该等于(p^m)减去(p^m)中(p)的所有倍数的个数。因为(p^m=p imes p imes pcdots p imes pquad (m个p))，那么显然，(p)的倍数一共会有(p^{m-1})个。那么原式可化为：
求欧拉函数
根据算术基本定理，任何的一个正整数都可以被唯一分解成若干个质数的积，即：
我们任取一个数(p)做(n)的质因子，只论(p)的话，那么显然，(p)的倍数都应该被排除掉。同理，如果又有一个(q)也为(n)的质因子，那么(q)的所有倍数也应该被刨除掉。那么还是根据容斥原理，(p,q)的公倍数被排除了两遍，所以需要把多排除的那遍加回来。所以就应该是：
那么，再结合上面的算术基本定理，我们求欧拉函数的通式就应该是：
那么，我们显然可以将其在质因数分解的过程中顺便求出来。
代码：
int Phi(int n)
{
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;
}
积性函数及其相关性质
首先放一波积性函数的定义：
如果当(a,b)互质的时候，函数(f(x))满足(f(ab)=f(a) imes f(b))，那么(f(x))就是一个积性函数。
显然欧拉函数是个积性函数（乘法原理）。
积性函数有很多种应用，比如欧拉函数，狄利克雷卷积，莫比乌斯反演等等（滑稽）。但是蒟蒻不会（滑稽）
线性筛选欧拉函数
当你要求(1-n)的欧拉函数的时候，刚刚的求欧拉函数的方式就比较鸡肋了。所以我们搞出了一个更快的方法——线筛与欧拉函数结合。
其实就是线筛素数，顺便就把欧拉函数也求出来了。
如果有对线筛素数不太熟悉的同学，可以移步这篇博客：
代码：
void euler(int n)
{
cnt=0;
for(int i=2;i<=n;i++)
{
if(!v[i])
prime[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=n && i*prime[j]<=n;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
稍微解释一下这段代码。着重解释一下对(phi[])数组的处理。
首先，当确定一个数为质数的时候，这个数的欧拉函数就是这个数减一，这个性质在上面有证明。
然后，在线筛模板上，如果(prime[j])为(i)的一个质因子，那么根据上面的性质，(i imes prime[j])的所有质因子都已经被(i)包括了。因为欧拉函数是个积性函数，所以else语句后的语句也可以被解释。
差不多就是这样？