本文主要是介绍【模板】AcWing873. 《欧拉函数》(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【题目描述】
给定 n 个正整数 ,请你求出每个数的欧拉函数。
欧拉函数的定义
【输入格式】
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 。
【输出格式】
输出共 n 行,每行输出一个正整数 的欧拉函数。
【数据范围】
1≤n≤100,
1≤ai≤2×
【输入样例】
3
3
6
8
【输出样例】
2
2
4
【代码】
#include<iostream>
using namespace std;
int phi(int x){int res = x;for(int i = 2;i<=x / i;i++){if(x % i == 0){res = res / i * (i - 1);}while(x % i == 0) x/= i;}if(x > 1) res = res / x * (x - 1);return res;
}
int main(){int n;cin >> n;while(n--){int a;cin >> a;cout << phi(a) << endl;}return 0;
}
这篇关于【模板】AcWing873. 《欧拉函数》(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!