如何计算62题中的欧拉函数？
摘要：62.Acwing基础课第873题-简单-欧拉函数 题目描述 (给定 n 个正整数 a_i，请你求出每个数的欧拉函数)。 欧拉函数的定义 (1 sim N) 中与 (N) 互质的数的个数被称为欧拉函数，记为 (phi(N
62.Acwing基础课第873题-简单-欧拉函数
题目描述
\(给定 n 个正整数 a_i，请你求出每个数的欧拉函数\)。
欧拉函数的定义
\(1 \sim N\) 中与 \(N\) 互质的数的个数被称为欧拉函数，记为 \(\phi(N)\)。
若在算数基本定理中，\(N = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}\)，则：
\[\phi(N) = N \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \dots \times \frac{p_m - 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
代码：
// 包含输入输出流头文件（cin/cout依赖）
#include <iostream>
// 使用std命名空间，避免重复写std::
using namespace std;
// 计算单个整数x的欧拉函数φ(x)
// 欧拉函数定义：1~x中与x互质的数的个数
int phi(int x)
{
// 初始化结果为x（欧拉函数公式的初始值）
int res = x;
// 质因数分解核心：枚举2到√x的所有数（i<=x/i等价于i<=sqrt(x)，避免浮点运算误差）
for (int i = 2; i <= x / i; i ++ )
// 若i是x的质因子（能整除x）
if (x % i == 0)
{
// 欧拉函数核心公式：φ(x) = x × (p1-1)/p1 × (p2-1)/p2 × ... × (pn-1)/pn
// 先除后乘：res/i*(i-1) 避免中间结果溢出（若先乘后除可能超出int范围）
res = res / i * (i - 1);
// 循环除净x中所有的质因子i（确保后续i都是新的质因子）
while (x % i == 0)
x /= i;
}
// 若循环结束后x>1，说明x本身是一个大于√原数的质因子，需补充计算
if (x > 1)
res = res / x * (x - 1);
// 返回最终的欧拉函数值
return res;
}
int main()
{
int n; // n：测试用例的组数
cin >> n; // 输入测试用例组数
// 循环处理n组测试用例
while (n -- )
{
int x; // x：需要计算欧拉函数的整数
cin >> x; // 输入待计算的整数
cout << phi(x) << endl; // 输出φ(x)的结果
}
return 0; // 程序正常结束
}