欧拉函数——acwing

题目一：欧拉函数

873. 欧拉函数 - AcWing题库

分析（欧拉函数相关知识点）

互质数不了解可以参考之前笔记，以便更好了解：

数论—快速幂，欧几里得及其扩展，逆元，单位元_数论单位元函数-CSDN博客

👆👆👆

代码

核心公式，只需要对n实现质因子分解即可：

质数——acwing-CSDN博客

👆👆👆质数的笔记

#include<bits/stdc++.h>
using namespace std;

int main() {
    int _;
    cin >> _;
    while(_ --) {
        int x; cin >> x;
        int ans = x; // 个数
        int i;
        for(i = 2; i <= x/i; i ++) {
            if(x%i == 0) {// 质因子判断
                // 先出后乘防止爆数据
                ans = ans/i*(i-1);
                // 先把i用了，然后约尽质因子i就可
                while(x%i==0) x/=i;
            }
        }
        
        if(x>1) ans = ans/x*(x-1);
        
        cout << ans << endl;
    }
    
    return 0;
}

题目二：筛法求欧拉函数 

874. 筛法求欧拉函数 - AcWing题库

分析

首先考虑暴力，但是每次都要求质因数分解。

算法优化：使用欧拉筛，来求欧拉函数，属于一种递推

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

//欧拉筛
const int N = 1e6+10;
int prime[N], cnt;
bool vis[N];
//欧拉函数
int ol[N];

int main() {
    int n;
    cin >> n;
    
    memset(vis,true,sizeof vis);
    ol[1] = 1;
    ll res = 0;
    
    for(int i = 2; i <= n; i ++) {
        if(vis[i]) {
            prime[cnt++] = i;
            
            ol[i] = i-1;
        }
        for(int j = 0; j < cnt && i*prime[j]<=n; j ++) {
            vis[i*prime[j]] = false;
            if(i%prime[j]==0) {
                
                ol[i*prime[j]] = ol[i]*prime[j];
                
                break;
            }
            ol[i*prime[j]] = ol[i]*(prime[j]-1);
        }
    }
    
    for(int i = 1; i <= n; i ++) {
        res += ol[i];
    }
    
    cout << res << endl;
    
    return 0;
}