欧拉函数
欧拉函数，即 \(\varphi(n)\)，表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数，详细定义看wiki。
欧拉函数其实就是容斥原理的应用，举个例子：
如 \(n=6\)，\(1,2,3,4,5,6\) 是整个序列，我们将 \(6\) 的质因子 \(2\)，\(3\) 取出，减去小于等于 \(6\) 的 \(2\) 的倍数和 \(3\) 的倍数，但是 \(2\) 和 \(3\) 的公倍数 \(6\) 被减了两次所以还要再加一次：\(6-\frac{6}{2}-\frac{6}{3}+\frac{6}{6}=2\)
将这个公式转化一下就可以得到通用公式（\(p\) 为 \(n\) 的质因数）:
\[\varphi(n)=n\times (1- \frac{n}{p_1})\times (1- \frac{n}{p_2}) \times ……\times (1- \frac{n}{p_k}) \]看什么代码，自己写
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
cin>>n;
m=n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
m*=(1-1.0/i);
while(n%i==0){
n/=i;
}
}
}
if(n>1){
m*=(1-1.0/n);
}
cout<<m<<"\n";
}
return 0;
}