摘要
Title: 874. 筛法求欧拉函数
Tag: 欧拉函数、线性筛
Memory Limit: 64 MB
Time Limit: 1000 ms

874. 筛法求欧拉函数

题意

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
思路

可以利用线性筛把欧拉函数也筛出来
递推式为

$φ(ab)= \frac{φ(a)φ(b)gcd(a,b)}{φ(gcd(a,b))}$

所以可以推出来：
- $φ(primes[j]) = primes[j] - 1$
- 当i % primes[j] == 0 , $φ(i * primes[j]) = φ(i) * primes[j]$
- 当i % primes[j] != 0 , $φ(i * primes[j]) = φ(i) * (primes[j] - 1)$
ps: phi[1] = 1 别忘了初始化

代码

'''
Author: NEFU AB-IN
Date: 2022-03-10 20:28:12
FilePath: \ACM\Acwing\874.py
LastEditTime: 2022-03-10 20:28:13
'''
N = int(1e6 + 10)
st, phi, prime = [0] * N, [0] * N, [0] * N


def init(n):
    res, cnt = 0, 0
    phi[1] = 1
    for i in range(2, n + 1):
        if st[i] == 0:
            prime[cnt] = i
            phi[i] = i - 1
            cnt += 1
        j = 0
        while i <= n // prime[j]:
            st[i * prime[j]] = 1
            if i % prime[j] == 0:
                phi[i * prime[j]] = phi[i] * prime[j]
                break
            phi[i * prime[j]] = phi[i] * (prime[j] - 1)
            j += 1
    for i in range(1, n + 1):
        res += phi[i]
    print(res)


n = int(input())
init(n)

874. 筛法求欧拉函数

题意

思路

代码