题目链接:https://www.acwing.com/problem/content/description/875/
题目叙述:
给定 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
思路
这题直接分解质因数以后套公式就行了,唯一注意的是公式需要变形,得先除以pk,再乘以pk-1
代码如下:
#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){
res=res/i*(i-1);
while(a%i==0) a/=i;
}
}
if(a>1) res=res/a*(a-1);
cout<<res<<endl;
}
return 0;
}
标签:正整数,函数,int,res,AcWing873,ai,欧拉
From: https://www.cnblogs.com/Tomorrowland/p/18322476