欧拉函数(Euler Function)

Cover

欧拉函数

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目(φ(1)=1)。此函数以其首名研究者欧拉命名(Euler'so totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。

定理

• phi(1) = 1
• 如果n是质数的话，phi(n) = n - 1
• 设m和n是互质的正整数，那么phi(mn) = phi(m) * phi(n)
• 当n为奇数时，phi(2n) = phi(n)
• 计算公式 phi(n) = n * (1 - 1 / p₁) \ * (1 - 1 / p₂) * … * (1 - 1 / p_k)

根据计算公式的代码实现

int phi(int n)
{
    int res = n;
    for(int i = 2; i <= n; i++)
    {
        if(n % i == 0)
        {
            n/=i;
            res = res - res / i;
        }
        while(n % i == 0)
            n/=i;
    }
    return res;
}

由分析可以知道，这个函数的时间复杂度为O(n)，当n达到1e9，肯定会超时。由于任何一个合数都存在着至少一个不大于sqrt(n)的质因数，所以只需遍历到sqrt(n)即可，这样时间复杂度为O(sqrt(n))。

改良代码

int phi(int n)
{
    int res = n;
    for(int i = 2; i * i <= n; i++) //降低时间复杂度
    {
        if(n % i == 0)
        {
            n/=i;
            res = res - res / i;
        }
        while(n % i == 0)
            n/=i;
    }
    if(n > 1) // 因为是遍历到sqrt(n)，所以可能存在未除尽或者n本身就为质数的情况
        res = res - res / n; 
    return res;
}

欧拉函数的应用

[POJ 2407 Relatives](2407 — Relatives)

题意 输出输入数据的欧拉函数数值 裸欧拉函数题

#include<iostream>
using namespace std;
int n;
int phi(int n)
{
    int res = n;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            n/=i;
            res = res - res / i;
        }
        while(n % i == 0)
            n/=i;
    }
    if(n > 1)
        res = res - res / n; 
    return res;
}
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        printf("%d\n",phi(n));
    }
    return 0;
}

HDU 2588 GCD

题意 求满足 1<=x<=N GCD(x_i , N) = a >= M 的个数
思路
由于本题数据范围达到1e9,正常GCD累加做法肯定会超时，所以推导公式
GCD(a * p_i , N) = a => GCD(p_i , N/a) = 1 => 求 1~N/a的欧拉函数的和
根据定理得 N%i == 0 phi(N/i) N%(N/i) == 0 phi(i)

#include<iostream>
using namespace std;
int T,n,m,sum;
int phi(int x)
{
    int res = x;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0)
        {
            res = res - res / i;
            x/=i;
        }
        while(x % i == 0)
            x/=i;
    }
    if(x > 1)
        res = res - res / x; 
    return res;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        sum = 0;
        scanf("%d%d",&n,&m);
        for(int i = 1; i * i <= n; i++)//降低时间复杂度所以遍历到sqrt(n)
        {
            if(n % i == 0)
            {
                if(i >= m)//计算根号左边的欧拉函数值
                    sum += phi(n/i);
                if(n / i != i && n / i >= m)//判断是否重复数，避免重复计算 计算根号右面的欧拉函数值
                    sum += phi(i);
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

HDU 2824 The Euler function

题意 计算给定范围内欧拉函数值的前缀和
思路 根据计算公式 使用筛法求素数近似方法来打表计算每个数的欧拉函数值
解释
计算1~8的欧拉函数值
phi(1) = 1，所以从2开始 phi(2) = 2 * (1 - 1 / 2) = 1 phi(4) = 4 * (1 - 1 / 2) = 2
phi(6) = 6 * (1 - 1 / 2) = 3 phi(8) = 8 * (1 - 1 / 2) = 4
3开始，phi(3) = 3 * (1 - 1 / 3) = 2 phi(6) = 3 * (1 - 1 / 3) = 2
4不是素数，跳过。
5开始，phi(5) = 5 * (1 - 1 / 5) = 4
6不是素数，跳过。
7开始，phi(7) = 7 * (1 - 1 / 7) = 6
8不是素数，跳过。
phi(1) = 1
phi(2) = 1
phi(3) = 2
phi(4) = 2
phi(5) = 4
phi(6) = 2
phi(7) = 6
phi(8) = 4
输出结果1~8 的欧拉函数值的和为22

#include<iostream>
#define Maxn 3000005
using namespace std;
int n,m,i,eul[Maxn];
long long sum;
void getphi(int n)
{
    for(int i = 1; i <= Maxn; i++)
        eul[i] = i;
    for(int i = 2; i <= Maxn; i++)
        if(i == eul[i])
            for(int j = i; j <= Maxn; j+=i)
                eul[j] = (eul[j] / i) * (i - 1);
}
int main()
{
    getphi(Maxn);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i = n,sum = 0; i <= m; i++)
            sum += eul[i];
        printf("%lld\n",sum);
    }
    return 0;
}