欧拉函数（Euler’s Totient Function），通常用符号$φ(n)$表示，用于计算小于或等于正整数$n$且与$n$互质的正整数的个数。欧拉函数具有以下性质：

1. 若$p$为质数，则$φ(p) = p - 1$，因为质数与小于它的所有数都互质。
2. 若$p$为质数，则对于任意正整数$k$，$φ(p^k) = p^k - p^(k-1)$，即$p$的$k$次幂与小于它的所有倍数都不互质。
3. 若$a$和$b$互质，则$φ(a * b) = φ(a) * φ(b)$，即两个互质数的乘积的欧拉函数等于各自的欧拉函数的乘积。

欧拉函数的公式为：

$\phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$

其中，$n$是正整数，$p_1, p_2, \ldots, p_k$ 是 $n$的所有不同的质因数。

这个公式表示，欧拉函数 $\phi(n)$ 可以通过将 $n$ 分解为质因数的乘积，并根据质因数的个数和值来计算。每个质因数 $p_i$ 的贡献是 $1 - \frac{1}{p_i}$，表示小于或等于 $n$ 且与 $p_i$不互质的数的比例。将所有质因数的贡献相乘，即得到$\phi(n)$ 的值。

例子

假设我们要计算欧拉函数 $\phi(12)$。

首先，将 $12$ 分解为质因数的乘积：$12 = 2^2 \cdot 3^1$。

然后，根据欧拉函数的公式，计算每个质因数的贡献并相乘：

$\phi(12) = 12 \cdot \left(1 - \frac{1}{2}\right) \cdot \left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$

因此，$\phi(12) = 4$，即小于或等于 $12$ 且与 $12$ 互质的正整数的个数为 $4$。这些正整数分别是 $1, 5, 7, 11$。

注意：欧拉函数主要用于计算与某个正整数互质的正整数的个数，而不是直接计算质因数分解后的结果。

#include <iostream>  // 包含输入输出流头文件

using namespace std;  // 使用std命名空间

int phi(int x) {  // 定义函数phi，计算欧拉函数值
    int res = x;  // 初始化结果为x
    for (int i = 2; i <= x / i; i ++)  // 遍历2到x的平方根
        if (x % i == 0) {  // 如果x能被i整除，说明i是x的一个质因子
            res = res / i * (i - 1);  // 更新结果res，用于计算欧拉函数值，res = res * (1 - 1 / i)
            while (x % i == 0) x /= i;  // 将x中的所有i因子除掉
        }
    if (x > 1) res = res / x * (x - 1);  // 处理x中剩余的质因子

    return res;  // 返回欧拉函数值
}

int main() {  // 主函数
    int n;  // 定义变量n，表示输入的测试用例数量
    cin >> n;  // 输入测试用例数量

    while (n --) {  // 循环处理每个测试用例
        int x;  // 定义变量x，表示输入的整数
        cin >> x;  // 输入整数x
        cout << phi(x) << endl;  // 输出x的欧拉函数值
    }

    return 0;
}