欧拉函数.
欧拉函数
给定 n个正整数 ai,请你求出每个数的欧拉函数。
欧拉函数的定义
输入格式
第一行包含整数 n。
接下来 n行,每行包含一个正整数 ai。
输出格式
输出共 n行,每行输出一个正整数 ai的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例:
3
3
6
8
输出样例:
2
2
4
#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;
}