欧拉函数φ

欧拉函数

欧拉函数，即 \(\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;
}