AcWing 874. 筛法求欧拉函数（欧拉函数）

题目链接

https://www.acwing.com/problem/content/876/

思路

对于一个数x如果是质数，那么它的欧拉函数就为 x − 1 x-1 x−1，对于其他合数我们可以将其拆成最小的质数的积，那么这个过程我们就可以通过欧拉筛法来计算欧拉函数值，现在我们还有两种情况需要讨论

• 如果i能整除prime[j]说明prime[j]是i的一个质因子，那么对于i*prime[j]来说其实就是 p h i [ i ] ∗ p r i m e [ j ] phi[i] * prime[j] phi[i]∗prime[j]
• 如果i不能整除prime[j]说明prime[j]不是i的质因子，那么我们最后需要乘上一个 1 − 1 p r i m e [ j ] 1-\frac{1}{prime[j]} 1−prime[j]1​所以也就是 p h i [ i ] ∗ ( p r i m e [ j ] − 1 ) phi[i] * (prime[j] - 1) phi[i]∗(prime[j]−1)

代码

#include 
using namespace std;
#define ll long long

const int N = 1e6+10;

ll phi[N],prime[N];
bool vis[N];


ll cal_oular(int n){
    phi[1] = 1;
    for(int i = 2;i