题目描述

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

欧拉函数的定义

$1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为$\varphi(n)$。
若在算数基本定理中，$N = p_1^{\alpha_1} * p_2^{\alpha_2} * p_3^{\alpha_3} … * p_m^{\alpha_m}$，则：
$\varphi(n) = N(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})…(1-\frac{1}{p_m})$

输入格式

第一行包含整数 $n$。

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

输出格式

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

数据范围

$ 1≤n≤100, $
$ 1≤a_i≤2×10^9 $

样例

输入样例：

3
3
6
8

输出样例：

2
2
4

算法

欧拉函数 分解质因数

时间复杂度

$O(n\sqrt{(a_i)})$

参考文献

C++ 代码

#include <iostream>
#include <algorithm>

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)   // 说明i是a的质因数
            {
                // φ(N) 公式(求欧拉函数的公式)
                res = res / i * (i - 1);

                while(a % i == 0) a /= i;

            }
        if (a > 1) res = res / a * (a - 1);
        cout<<res<<endl;
    }
}

// 分解质因数
void divid(int x)
{
    for (int i=2; i <= x/i; i++)    // n 中只包含一个大于 sqrt(n) 的质因子
        if (x % i == 0) //说明i是x的质因数
        {
            // 使用循环计算i的次数(指数)
            int s=0;    // s用于记录质因子 i 的指数
            while (x % i ==0)
            {
                x /= i;
                s ++;
            }

            printf("%d %d\n", i, s);
        }
    if (x > 1) printf("%d %d\n", x, 1);
    printf("\n");

}