欧拉函数

概念引入

1. 互质: 如果两个数的最大公约数是1，则称这两个数互质。

2. 欧拉函数: 在1~N中与N互质的数的个数被称为欧拉函数，记作：φ（N） 假如对这个正整数按照算术基本定理分解，就可按照下图的流程，推导出欧拉函数的计算公式

公式法求欧拉函数

算法模板

实现流程图：

算法的代码描述如下：

公式法求欧拉函数
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

例题描述

参考代码(C++版本)

疑难点剖析

一、分解质因数是基础

对分解质因数的算法模板要清楚，假如对分解质因数比较模糊的小伙伴可以看看这篇文章喔，也是挂过热榜的，值得信赖呀

二、欧拉函数的计算公式

记得住最好，假如记不住了，可以利用容斥原理，自己推理两三个数据就可以发现规律喔

让我好好想想

线性筛法求欧拉函数

公式法求欧拉函数适用于只求少量数据的欧拉值，倘若题目要求很多数据的欧拉值或者欧拉值的乘积、和。那么公式法就可能TLE，因此，借助线性筛法的模板来优化求公式法求欧拉值的过程。

算法模板

算法实现流程图：

算法模板代码实现：

筛法求欧拉函数
int primes[N], cnt;   // primes[]存储所有素数
int phi[N];     // 存储每个数的欧拉函数
bool st[N];     // st[x]存储x是否被筛掉
void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                phi[t] = phi[i] * primes[j];
                break;
            }
            phi[t] = phi[i] * (primes[j] - 1);
        }
    }
}

例题描述

参考代码(C++版本）

疑难点剖析

一、线性筛法的难点在于如何结合公式统计出当前参数的欧拉值，将相应结果存放到phi数组中。

情况一：当前这个数据是质数。 与质数n互质的数的个数有n-1个。比如质数7。1~6与它的最大公约数都是1,互质的个数就是6。因此可以得到phi[n] = n-1；

情况二：筛选中，当前这个质数primes[j]是i的质因数 phi[primes[j] * i] 可变型为phi[primes[j] ] * phi[i] 。因为primes[j]是i的质因数，所以在用公式算phi[i]的时候就已经把(1-1/primes[j])算了。所以对于phi[primes[j]]就只用将剩下的primes[j]乘上。 因此 phi[primes[j] * i] = phi[i]*primes[j];

情况三：筛选中，当前这个质数primes[j]不是i的质因数。 因为primes[j]不是质因数了，就得独立的对它进行公式计算，即phi[ primes[j] ] = primes[j] x (1 - 1/primes[j]) x phi[i] 因此，结果为： phi[primes[j] * i] = phi[i]*(primes[j]-1);

二、注意范围，因为题目所给的数据就能很大，统计欧拉值的时候以乘积的形式统计的，可能会造成溢出。对于数论的题，可以泛泛而谈大多数时候都是要用long long 类型的，因为所给的数据一般比较大，比如2 x 10^9。假如再进行乘法运算，就会溢出