【暖*墟】#数论# 欧拉函数的学习与练习

欧拉函数的定义

?(n)：对于整数n，小于等于n、且与n互质的正整数的个数。

欧拉函数的计算方法

√n计算单值欧拉函数：计算?(n)，分情况讨论。

1.当n=1时，很明显，答案为1。

2.当n为质数时，根据素数的定义，答案为n−1。

3.当n为合数时，对n进行质因数分解：设n=a1^p1∗a2^p2...∗ak^pk，

（1）假设k=1，即n=a1^p1、只有一个因数就是素数a1。

• 那么：?(p^k)=p^k−p^(k−1)。

• 证明：容斥原理知，答案=n-与它不互素的数的个数，
• p是素数，在p^k中与其不互素的数为1∗p,2∗p....p^(k−1)∗p，共p^(k−1)个。

（2）当k≠1时，?(n)=?(a1^p1∗a2^p2...∗ak^pk)。

• 通过k=1求得的性质可知：

?(n) = ∏(i=1~k)ai^Pi−ai^(Pi−1)

        = ∏(i=1~k)(ai^Pi)*(1-1/ai)

        = n∗∏(i=1~k)(1-1/ai)

        = n∗∏(i=1~k)((ai-1)/ai);

int euler(int x){
    int ans=x;
       for(int i=2;i*i<=x;i++)
        if(x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
    } if(x>1) ans=ans/x*(x-1);
    return ans; //返回?(x)的值
}

欧拉函数的性质

1.?(n)为积性函数。即：gcd(a,b)=1时，?(ab)=?(a)*?(b)。

积性函数：若一个定义在正整数域上的函数f(x)，

对于任意满足gcd(x,y)==1的x、y都有f(xy)=f(x)∗f(y)。

常见积性函数：莫比乌斯函数μ(n)，欧拉函数?(n)，

一个数n的约数个数d(n)，一个数n的约数和σ(n)，f(x)=x^k(k∈N)......

证明欧拉函数是积性函数：

狄利克雷卷积：若 f(x),g(x) 都是积性函数，则狄利克雷卷积 h(x)=∑(d|x)f(d)*g(x/d) 。

• 性质：若f(x),g(x)都是积性函数，则狄利克雷卷积也是积性函数。

积性函数的性质：任意积性函数都可以线性筛（在严格O(n)时间复杂度内筛出）。

2.∑(d|n)?(d)=n。

3.1到n中与n互质的数的和为n∗?(n)/2 (n>1)。

• 证明：若gcd(n,i)=1，那么gcd(n,n−i)=1。
• 即，与n互质的数都是成对出现的。且每一对的和都为n。

4. a^(?(n))≡1(modn)。

欧拉函数的线性筛法

利用三个性质：

性质1 若p为素数，则φ(p)=p−1。

性质2 若i mod p≠0 ，且p为素数，则φ(i∗p)=φ(i)∗φ(p)=φ(i∗p)=φ(i)∗(p−1)。

性质3 若i mod p=0 ，且p为素数，则φ(i∗p)=φ(i)∗p。详情见 这里

int phi[MAXN],vis[MAXN],prime[MAXN],tot=0;

void GetPhi(int n){
    phi[1]=1; //特例：?(1)=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) prime[++tot]=i,phi[i]=i-1; //i是素数（1）
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){ //枚举“i*质数”
            vis[i*prime[j]]=1; //标记“i*质数”为合数
            if(i%prime[j]==0) //（3）注意这里可以直接break;
             {phi[i*prime[j]]=phi[i]*prime[j];break;}
            else phi[i*prime[j]]=phi[i]*(prime[j]-1); }//（2）
    } for(int i=1;i<=n;i++) cout<<phi[n]<<endl;
}

【暖*墟】#数论# 欧拉函数的学习与练习

原文：https://www.cnblogs.com/FloraLOVERyuuji/p/10423022.html