8.欧拉函数

 

用定义求欧拉函数 

互质是公约数只有1的两个整数，叫做互质整数

φ（6）= 2。1 2 3 4 5 6中和6互质的数是1和5

求一个数的欧拉函数的话，需要对这个数先分解质因数

 证明方法：容斥原理

 时间复杂度O(sqrt(n))

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        int res = a;
        for (int i = 2; i <= a / i; i++) { //分解质因数
            if (a % i == 0) {
                res = res  / i * (i - 1); //公式,避免小数，交换顺序
                while (a % i == 0) {
                    a /= i;
                }
            }
        }
        if (a > 1) {
            res = res / a * (a - 1);
        }
        cout << res << endl;
    }
    return 0;
}