[数据结构与算法]AcWing 874. 筛法求欧拉函数详细题解

题目来源AcWing 874. 筛法求欧拉函数详细题解

思路

整体思路为在使用线性筛法的同时将每个 i 的欧拉函数得到。

代码

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 1000010;
int prime[N], cnt;
bool st[N];
int euler[N];

void get_eulers(int n)
{
    euler[1] = 1; //使得欧拉函数的初始值为 1
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) //当 i 为质数时
        {
            prime[cnt ++] = i;
            euler[i] = i - 1; //显然，i为质数的话，有 i - 1 对互质对
        }
        for (int j = 0; prime[j] * i <= n; j ++)
        {
            st[prime[j] * i] = true; //没有被标记的即为质数
            if (i % prime[j] == 0) //此时的prime [j] 为 i的最小质因子
            {
                euler[prime[j] * i] = euler[i] * prime[j];// 公式可以记忆为将prime[j]看做是一个常数，则
                //那么 euler[prime[j] * i] 就会得到以上结果
                break;
            }
            else
            {
                euler[prime[j] * i] = euler[i] * (prime[j] - 1); //此时不是最小质因子，不知道咋解释，背吧
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    
    get_eulers(n);
    
    LL res = 0;
    for (int i = 1; i <= n; i ++) res += euler[i];
    
    cout << res << endl;
    
    return 0;
}