AcWing - 欧拉函数(数论)

题目链接:https://www.acwing.com/problem/content/description/875/
时/空限制：1s / 64MB

题目描述

给定n个正整数ai，请你求出每个数的欧拉函数。

欧拉函数的定义

1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)。
若在算数基本定理中，，则：

输入格式

第一行包含整数n。

接下来n行，每行包含一个正整数ai。

输出格式

输出共n行，每行输出一个正整数ai的欧拉函数。

数据范围

1≤n≤100,
1≤ai≤2∗10^9

输入样例

3
3
6
8

输出样例

2
2
4

解题思路

题意:求一个数的欧拉函数。
思路:直接套用上面的公式就行了，注意最后n不为1的情况，证明最后这个n也是它的质因子。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
int Euler(int n) {
    int cnt = n;
    for (int i = 2; i <= n / i; i++) {
        if (!(n % i)) {
            cnt = cnt / i * (i - 1);
            while (!(n % i))
                n /= i;
        }
    }
    if (n > 1)
        cnt = cnt / n * (n - 1);
    return cnt;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        printf("%d\n", Euler(x));
    }
    return 0;
}