AcWing 873. 欧拉函数如何计算？
- 内容介绍
- 文章标签
- 相关推荐
本文共计473个文字，预计阅读时间需要2分钟。
题目：给定一个整数序列 $\{a_i\}$，求出每个数的欧拉函数 $\varphi(n)$。
定义：欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 的正整数中，与 $n$ 互质的数的个数。
若在算数基本定理中，$N=\{p_1\}^{a_1}\{p_2\}^{a_2}$，则 $\varphi(N)$ 的计算公式为：
$$\varphi(N)=N \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \cdots \times \left(1 - \frac{1}{p_k}\right)$$
其中，$p_1, p_2, \ldots, p_k$ 是 $N$ 的所有不同质因数。
题目
给定 $n$ 个正整数 $a_i$，请你求出每个数的欧拉函数。
欧拉函数的定义 $1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。 若在算数基本定理中，$N={p_1}^{a_1}{p_2}^{a_2}...{p_m}^{a_m}$，则：$\varphi(n) = m(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k)$ 输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个正整数 $a_i$。
输出格式 输出共 $n$ 行，每行输出一个正整数 $a_i$ 的欧拉函数。
数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：
3
3
6
8
输出样例：
2
2
4
思路
由欧拉函数有关性质，对于一个正整数，求其欧拉函数结果的公式为：$\varphi(n) = m(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k)$，其中 $p_i$ 为 $n$ 的质数。
代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> 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);
cout << res << endl;
}
return 0;
}
本文共计473个文字，预计阅读时间需要2分钟。
题目：给定一个整数序列 $\{a_i\}$，求出每个数的欧拉函数 $\varphi(n)$。
定义：欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 的正整数中，与 $n$ 互质的数的个数。
若在算数基本定理中，$N=\{p_1\}^{a_1}\{p_2\}^{a_2}$，则 $\varphi(N)$ 的计算公式为：
$$\varphi(N)=N \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \cdots \times \left(1 - \frac{1}{p_k}\right)$$
其中，$p_1, p_2, \ldots, p_k$ 是 $N$ 的所有不同质因数。
题目
给定 $n$ 个正整数 $a_i$，请你求出每个数的欧拉函数。
欧拉函数的定义 $1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。 若在算数基本定理中，$N={p_1}^{a_1}{p_2}^{a_2}...{p_m}^{a_m}$，则：$\varphi(n) = m(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k)$ 输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个正整数 $a_i$。
输出格式 输出共 $n$ 行，每行输出一个正整数 $a_i$ 的欧拉函数。
数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：
3
3
6
8
输出样例：
2
2
4
思路
由欧拉函数有关性质，对于一个正整数，求其欧拉函数结果的公式为：$\varphi(n) = m(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k)$，其中 $p_i$ 为 $n$ 的质数。
代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> 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);
cout << res << endl;
}
return 0;
}