筛法求欧拉函数

原题链接：874. 筛法求欧拉函数 - AcWing题库

前导知识

如果i和j互质，则φ(i) * φ(j) = φ(i * j)

证明：

φ(i) * φ(j) = i * [(1 - 1/p1) * (1 - 1/p2)…] * j * [(1 - 1/q1) * (1 - 1/q2)…] p1,p2…为i的质因子即 q1,q2…为j的质因子

φ(i * j) = (i * j) * (1 - 1/r1) * (1 - 1/r2)… r1,r2…为i * j的质因子

i和j互质所以i和j的质因子都不相同，则[(1 - 1/p1) * (1 - 1/p2)…] * j * [(1 - 1/q1) * (1 - 1/q2)…]之间没有重复且包含(1 - 1/r1) * (1 - 1/r2)…的所有元素，所以[(1 - 1/p1) * (1 - 1/p2)…] * j * [(1 - 1/q1) * (1 - 1/q2)…] = (1 - 1/r1) * (1 - 1/r2)…

φ(i) * φ(j) = （i * j) * { [(1 - 1/p1) * (1 - 1/p2)…] * j * [(1 - 1/q1) * (1 - 1/q2)…] } = (i * j) * (1 - 1/r1) * (1 - 1/r2)…) = φ(i * j)

如果i为质数，则φ(i) = i - 1

因为质数的因数只有一和它本身，所以比i小的数都与i互质，也就是说在1 ~ i中有i - 1个数与i互质

解题思路

求解φ(x)可以分类讨论：

1：如果x是质数

φ(x) = x - 1

2：如果x = i * j，且x不是质数时

​ 2.1：如果j是i的最小质因子

​ φ(x) = φ(i * j) = (i * j) * (1 - 1/r1) * (1 - 1/r2)…

​ j的质因子已经被包含在i的质因子中所以：

​ φ(i) = i * (1 - 1/r1) * (1 - 1/r2)…

​ φ(i * j) = φ(i) * j

​ 2.2：如果j不是i的最小质因子，且j是质数时

​ i和j互质

​ φ(j) = j - 1

​ φ(x) = φ(i * j) = φ(i) * φ(j) = φ(i) * (j - 1)

这些可能性又可以整合到线性筛质数中即：

phi[1] = 1;
for(int i = 2;i <= n;i ++)
    {
        if(!st[i])//1: x为质数
        {
            prime[++ cnt] = i;
            phi[i] = i - 1;// φ(x) = x - 1
        }
        for(int j = 1;j <= n / i;j ++)
        {
            st[i * prime[j]] = true;
            if(i % prime[j] == 0)//2.1: x = i * j，j是i的最小质因子
            {
                phi[i * prime[j]] = phi[i] * prime[j];//φ(x) = φ(i) * j
                break;
            }
            //2.2: x = i * j，j不是i的最小质因子，且j是质数时
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);//φ(x) = φ(i) * (j - 1)
        }
    }

源代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int main()
{
    int n;
    int prime[N];
    bool st[N];
    int phi[N];
    int cnt = 0;

    phi[1] = 1;

    cin >> n;

    for(int i = 2;i <= n;i ++)
    {
        if(!st[i])
        {
            prime[++ cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= n / i;j ++)
        {
            if(i * prime[j] <= N)st[i * prime[j]] = true;//因为i * prime[j]可能很大所以要设置条件防止越界
            if(i % prime[j] == 0)
            {
                if(i * prime[j] <= N)phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            if(i * prime[j] <= N)phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }

    long long re = 0;
    for(int i = 1;i <= n;i ++)re += phi[i];
    cout << re;

    return 0;
}