地址 https://www.acwing.com/problem/content/875/
给定n个正整数ai,请你求出每个数的欧拉函数。 欧拉函数的定义
输入格式
第一行包含整数n。 接下来n行,每行包含一个正整数ai。 输出格式
输出共n行,每行输出一个正整数ai的欧拉函数。 数据范围
≤n≤,
≤ai≤∗
输入样例: 输出样例:
题解
模板题 根据公式可得代码中注释部分的代码 然后避免出现分数 调整了计算次序 并做了一些通分 方便计算
#include <iostream> using namespace std; int phi(int x)
{
int res = x;
for (int i = ; i <= x / i; i ++ )
if (x % i == )
{
res = res*(-/i); // = res*((i-1)/i) = res/i*(i-1)
//res = res / i * (i - 1); //最终结果
while (x % i == ) x /= i;
}
if (x > ) res = res / x * (x - ); return res;
} int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
cout << phi(x) << endl;
} return ;
}