给定 n n n 个正整数 ai,请你求出每个数的欧拉函数。
欧拉函数的定义1∼ N N N 中与 N N N 互质的数的个数被称为欧拉函数,记为 ϕ(N)。
若在算数基本定理中, N N N=p1a1p2a2…pmam, 则: ϕ ( N ) ϕ(N) ϕ(N) = N N N× p 1 − 1 p 1 \frac{p1 −1}{p1} p1p1−1× p 2 − 1 p 2 \frac{p2−1}{p2} p2p2−1×…× p m − 1 p m \frac{pm−1}{pm} pmpm−1
输入格式
第一行包含整数 n n n。
接下来 n n n 行,每行包含一个正整数 ai。
输出格式
输出共 n n n 行,每行输出一个正整数 ai 的欧拉函数。
数据范围
1 ≤ n ≤ 100 , 1 ≤ a i ≤ 2 × 109 1≤n≤100,1≤ai≤2×109 1≤n≤100,1≤ai≤2×109
输入样例:
3
3
6
8
输出样例:
2
2
4
对于 n n n,分解质因数后为: N N N=p1a1p2a2…pmam,那么欧拉函数的结果就是 ϕ ( N ) ϕ(N) ϕ(N) = N N N× p 1 − 1 p 1 \frac{p1 −1}{p1} p1p1−1× p 2 − 1 p 2 \frac{p2−1}{p2} p2p2−1×…× p m − 1 p m \frac{pm−1}{pm} pmpm−1,即运用此公式进行求欧拉函数的过程
代码:
#include<iostream>
using namespace std;
int main() {
int n; cin >> n;
while (n--) {
int a; cin >> a;
int res = a; //答案初始为a
for (int i = 2; i <= a / i; i++) {
//分解质因数
if (a % i == 0) {
//如果a整除i,那么是质因子
res = res / i * (i - 1); //( res = res * (1 - 1/i) )化简避免小数
while (a % i == 0) a /= i; //消倍数
}
}
if (a > 1) res = res / a * (a - 1); //如果有余下的质因子
cout << res << endl;
}
return 0;
}
筛法求欧拉函数代码:
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt; //存质数
bool st[N]; //判断哪个数被筛掉
int phi[N]; //存欧拉函数值
long long get_eulers(int n) {
phi[1] = 1; //1的欧拉函数值为1
for (int i = 2; i <= n; i++) {
if (!st[i]) {
//如果没有被筛过
primes[cnt++] = i; //说明i为质数
phi[i] = i - 1; //如果i是质数,那么欧拉函数值为i-1,因为1~i-1都与他互质
}
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = 1;
if (i % primes[j] == 0) {
//primes[j]是i的质因子
//phi(pj * i) = pj * phi(i)
phi[primes[j] * i] = primes[j] * phi[i];
break;
}
//如果不是,那么为( phi(pj * i) = phi(i) * ( pj - 1 ) )
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
long long res = 0;
for (int i = 1; i <= n; i++)res += phi[i];
return res;
}
int main() {
int n; cin >> n;
cout << get_eulers(n) << endl;
return 0;
}