欧拉函数(学习笔记)

欧拉函数： $\varphi(x)=x\prod\limits_{i=1}^n(1-\dfrac{1} {p_i})$ , $p_1,p_2\dots p_n$ 为 $x$ 的质因数。

$\varphi(1)=1$ . $ps:$ 每种质因数只有一个。

性质：

1. $\phi(n)=n-1,$ 当 $n$ 为质数。

证明：显然当 $n$ 为质数, $1\sim n-1$ 显然与 $n$ 互质。

$2.\varphi(ab)=\varphi(a)\times\varphi(b)$ ,当 $a,b$ 互质。

[特别地：当 $n$ 为奇质数时， $\varphi(2n)=\varphi(n)\times\varphi(2)=\varphi(n)$ ]

证明: $\varphi(x)$ 为积性函数，具体不详细证明。

3. $\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1},$ 当 $n$ 为质数 $p$ 的 $k$ 次幂。

证明：显然 $p$ 的倍数都不与 $n$ 互质，这样的数个数为 $\dfrac{n}{p}=p^{k-1}$

所以互质的个数为 $n-\dfrac{n}{p}=(p-1)p^{k-1}$

$4.\varphi(ab)=\varphi(a)\times b,$ 当 $a,b$ 互质，且 $b$ 为 $a$ 倍数。

证明：根据公式有： $\varphi(ab)=ab\prod\limits_{i=1}^n(1-\dfrac{1}{p_i})$ ,显然 $p_i$ 都为 $a$ 的质因子。

所以可改写为 $a\prod\limits_{i=1}^n(1-\dfrac{1}{p_i})\times b=\varphi(a)\times b$

接下来就可以用欧拉筛实现求欧拉函数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int is_prime[N],phi[N],p[N],cnt;
void Euler(int n){
     phi[1]=1;//初始化 
     for(int i=2;i<=n;i++)
     {
           if(!is_prime[i]) //如果是素数 
           {
                    p[++cnt]=i;
                    phi[i]=i-1;//性质1 
            }
                    for(int j=1;j<=cnt&&p[j]*i<=n;j++) //筛合数 
                {
                         is_prime[p[j]*i]=1;
                         if(i%p[j]==0){  //如果不是互质 
                                phi[p[j]*i]=phi[i]*p[j];//性质4 
                                break;
                         }
                     else phi[p[j]*i]=phi[p[j]]*phi[i];//性质2 
                } 
     }
}
int main(){
    int n; 
    scanf("%d",&n);
    Euler(n);
    for(int i=1;i<=n;i++)
        printf("phi(%d):%d\n",i,phi[i]);
    return 0;
}

方法2，利用公式计算。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int phi(int n){
    int ans=n;
    for(int i=2;i<=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;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",phi(n));
    }
    return 0;
}