768. 欧拉函数
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 给定 $n$ 个正整数 $a_i$，请你求出每个数的欧拉函数。 $1 \sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $ϕ(N)$。 若在算数基本定理中，$N=p_1^{a_1}p_2^{a_2} \cdots p_m^{a_m}$，则： $ϕ(N) = N \times \frac{ p_1-1}{p_1} \times \frac{ p_2-1}{p_2} \times \cdots\times \frac{ p_m-1}{p_m}$ ## 输入格式 第一行包含整数 $n$。 接下来 $n$ 行，每行包含一个正整数 $a_i$。 ## 输出格式 输出共 $n$ 行，每行输出一个正整数 $a_i$ 的欧拉函数。 ## 数据范围 $1 \le n \le 100$, $1 \le a_i \le 2 \times 10^9$ ## 输入 ```in1 3 6 8 ``` ## 输出 ```out1 2 4 ``` ## 提示