AOJ NTL_1_D Euler’s Phi Function & 欧拉函数相关




欧拉函数: 提供1到N中与N互质的数的个数.

定义和简单性质

欧拉函数用希腊字母φ(Phi)表示,φ(N)表示N的欧拉函数.

对φ(N)的值,我们可以通俗地理解为小于N且与N互质的数的个数(包含1).

性质

1.对于素数p,φ(p)=p-1,对于两个素数p,q φ(pq)=(p-1)*(q-1)

欧拉函数是积性函数,但不是完全积性函数.

证明:

函数的积性即:
若m,n互质,则φ(mn)=φ(m)φ(n).由“m,n互质”可知m,n无公因数,所以:
φ(m)φ(n)=m(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)·n(1-1/p1′)(1-1/p2′)(1-1/p3′)…(1-1/pn’)
其中p1,p2,p3…pn为m的质因数,p1′,p2′,p3’…pn’为n的质因数,而m,n无公因数,所以:
p1,p2,p3…pn,p1′,p2′,p3’…pn’
互不相同,所以:
p1,p2,p3…pn,p1′,p2′,p3’…pn’
均为mn的质因数且为mn质因数的全集,所以:
φ(mn)=mn(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)(1-1/p1′)(1-1/p2′)(1-1/p3′)…(1-1/pn’)
所以:
φ(mn)=φ(m)φ(n).

即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立(n与m互质).

2.对于一个正整数N的素数幂分解N=P1^q1P2^q2…*Pn^qn.

则 φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

3.除了N=2,φ(N)都是偶数.

4.设N为正整数,∑φ(d)=N (d|N)(d是N的质因数).

根据性质二,我们可以在O(sqrt(n))的时间内暴力求出一个数的欧拉函数值.

如果我们要求1000000以内所有数的欧拉函数,怎么办.

上面的方法复杂度将高达O(N*sqrt(N)).

暴力方法:

#include<iostream>
#include<algorithm>
using namespace std;

///返回euler(n)
int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int a[10]={2,10,100,1000,5,7,9,11,12,13};
    for(int i=0;i<10;++i)
        cout<<euler(a[i])<<endl;
    return 0;
}

结果:

我们可以将这个方法和筛法求素数的想法结合,试用筛法求出1~n内各个数字的euler(n).

φ(n)=n(1-1/p1)(1-1/p2)….(1-1/pk)
其中p1、p2…pk为n的所有素因子(这个素因子是由整数素分得来的)。
比如:φ(12)=12
(1-1/2)(1-1/3)=4。

比如求10以内所有数的φ值:

1.设一数组phi[11],赋初值phi[1]=1,phi[2]=2…phi[10]=10

2.然后从2开始循环

把2的倍数的φ值(1-1/2),则phi[2]=21/2=1,phi[4]=41/2=2,phi[6]=61/2=3….;

再是3,3的倍数的φ值(1-1/3),则phi[3]=32/3=2,phi[6]=3*2/3=2,phi[9]=…..;

再5,再7…因为对每个素数都进行如此操作,因此任何一个n都得到了φ(n)=n*(1-1/p1)(1-1/p2)….(1-1/pk)的运算

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;

///筛法求euler(1)~euler(n)
const int maxn=101;
int euler_1_n[maxn];

void a_euler(){
    euler_1_n[1]=1;
    for(int i=2;i<maxn;++i) euler_1_n[i]=i;
    for(int i=2;i<maxn;++i){
        if(euler_1_n[i]==i){
            for(int j=i;j<maxn;j+=i){
                euler_1_n[j]=euler_1_n[j]/i*(i-1);
            }
        }
    }
}

int main(){
    a_euler();
    for(int i=1;i<101;++i)
        cout<<euler_1_n[i]<<endl;

    return 0;
}

AOJ NTL_1_D Euler’s Phi Function

这道题数值范围是1e10,没超过int.而且只需要求一个数的euler.
O(lgn)暴力即可.

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

///返回euler(n)
int euler(int n){
    int res=n,a=n;
    for(int i=2;i*i<=a;++i){
        if(a%i==0){
            ///φ(N)=N*(1-1/P1)*(1-1/P2)...其中P是素因子
            res=res/i*(i-1);//先进行除法方为了预防溢出
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

int main(){
    int n;
    cin>>n;
    cout<<euler(n)<<endl;

    return 0;
}