【題目來源】
https://www.lanqiao.cn/problems/4330/learning/

【問題描述】
這是一道模板題。
首先給出歐拉函數的定義：即 φ(n) 表示的是小于等于 n 的數中和 n 互質的數的個數。
比如說 φ(6)=2，當 n 是質數的時候，顯然有φ(n)=n-1。

【題目大意】
給定 n 個正整數，請你求出每個數的歐拉函數。

【輸入格式】
輸入共兩行。
第一行輸入一個整數表示 n。
第二行輸入 n 個整數。

【輸出格式】
輸出共 n 行，每行輸出 1 個整數表示對應數字的歐拉函數。???????

【輸入樣例】
3
3 6 8???????

【輸出樣例】
2
2
4

【說明】
小于等于 3 的數中與 3 互質的有：1, 2。
小于等于 6 的數中與 6 互質的有：1, 5。
小于等于 8 的數中與 8 互質的有：1, 3, 5, 7。

【評測數據規模】
保證 1≤n≤100，輸入的 n 個整數范圍為 [1, 2×10^9]。

【算法分析】
● 歐拉函數 φ(n) 是數論中的重要函數，用于計算小于等于 n 的數中和 n 互質的數的個數。特別地，當 n=1 時，φ(1)=1。

● 歐拉函數的計算公式：若 N 的質因數分解為 N=p??1×p??2×...×p???，則 φ(N)=N×(1-1/p?)×(1-1/p?)×...×(1-1/p?)。其中，p?，…，p?，是 N 的所有質因數。
【例如， 由于 18=2×32，所以 φ(18)=18×(1-1/2)×(1-1/3)=6（表示 1~18 中與 18 互質的正整數有 1,5,7,11,13,17 等 6 個）。詳見：https://blog.csdn.net/hnjzsyjyj/article/details/148135689】

● 歐拉函數性質?
（1）若p是質數，φ(p)=p-1。
例如，φ(5)?=5-1=4（表示 1~5 中與 5 互質的正整數有 1,2,3,4 等 4 個）。
（2）若n=p?，φ(p?)=p?-p??1。
例如，φ(8)?=23-22=8-4=4（表示 1~8 中與 8 互質的正整數有 1,3,5,7 等 4 個）
（3）積性函數：當 a,b 互質時，φ(ab)=φ(a)φ(b)。
例如，φ(10)=φ(2)×φ(5)=1×4=4（表示 1~10 中與 10 互質的正整數有 1,3,7,9 等 4 個）
（4）通用計算公式：φ(N)=N×(1-1/p?)×(1-1/p?)×...×(1-1/p?)。其中，p?，…，p?，是 N 的所有質因數。

【算法代碼】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
int a[maxn];int oula(int x) {int ans=x;for(int i=2; i*i<=x; i++) {if(x%i==0) {ans=ans/i*(i-1);while(x%i==0) x/=i;}}if(x>1) ans=ans/x*(x-1);return ans;
}int main() {int n;cin>>n;for(int i=1; i<=n; i++) {cin>>a[i];cout<<oula(a[i])<<endl;}return 0;
}/*
in:
3
3 6 8out:
2
2
4
*/

【參考文獻】
https://blog.csdn.net/hnjzsyjyj/article/details/148159326
https://blog.csdn.net/hnjzsyjyj/article/details/148135689



?