欧拉函数

Problem

对于任意正整数 $n$，试问 $[1,n]$ 中，有多少正数与 $n$ 互质？

Idea

考虑容斥原理，求互质的个数，可以用总个数 $n$ 减去不互质的数字的个数。

求与 $n$ 其不互质的数字，原理上就是求 $\gcd(i,n)\neq1$ 的 $i$ 的数量，考虑分解质因数判断。

先预处理 $n$ 的质因数分解方案，即 $n={P_1}^{a_1}\times{P_2}^{a_2}\times{P_3}^{a_3}\dots{P_k}^{a_k}$。

记 $\varphi(x)$ 表示 $x$ 的欧拉函数，则根据容斥原理，有：

$\varphi(x)=$ 总情况数 $n$
减去所有单个质因子的情况：$-\frac n {P_1}-\frac n {P_2}-\dots-\frac n {P_k}$
加上所有两项之积：$+\frac n {P_1 P_2}+\frac n {P_1 P_3}+\dots+\frac n {P_2 P_3}+\dots+\frac n {P_{k-1} P_k} $
减去所有三项之积：$-\frac n {P_1 P_2 P_3}-\frac n {P_1 P_2 P_4}-\dots-\frac n {P_2 P_3 P_4}-\dots-\frac n {P_{k-2} P_{k-1} P_k}$
以此类推：$\dots$
直到所有项之积：$+(-1)^n \frac n {P_1 P_2\dots P_n}$

#include<bits/stdc++.h>
using namespace std;
int eular(int n) {
	int res=n,tot=n;
	vector<int> v;
	for(int i=2;i*i<=n;++i) {
		if(n%i) continue;
		res=res*(i-1)/i;
		while(n%i==0) n/=i;
	}
	if(n) res=res*(n-1)/n;
	return res;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int TT;
	cin>>TT;
	while(TT--) {
		int n;
		cin>>n;
		cout<<eular(n)<<'\n';
	}
	return 0;
}

筛法求欧拉函数

使用埃氏筛辅助算出每个数的质因子，可以快速地 $O(n)$ 预处理出 $1\sim n$ 中每个数的 $\varphi(x)$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+7;
ll el[N];
ll tot_eular(int n) {
	for(int i=1;i<=n;++i) el[i]=i;
	for(int i=2;i<=n;++i) {
		if(el[i]!=i) continue;
		for(int j=i;j<=n;j+=i)
			el[j]=el[j]*(i-1)/i;
	}
	ll res=0;
	for(int i=1;i<=n;++i) res+=el[i];
	//for(int i=1;i<=n;++i) cout<<el[i]<<' ';
	return res;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	cout<<tot_eular(n)<<'\n';
	return 0;
}