显然，本文的一切都是关于它——\(\varphi\)。
前提
互质
若有正整数 \(a,b\) 且满足 \(\gcd(a,b)=1\)，则称 \(a,b\) 互质。
对于多种数的情况，我们把 \(\gcd(a,b,c)=1\) 的情况称为 \(a,b,c\) 互质。把 \(\gcd(a,b)=\gcd(a,c)=\gcd(b,c)=1\) 称为 \(a,b,c\) 两两互质。后者明显是一个更强的条件。
正题·欧拉函数
含义
\(1~N\) 中所有与 \(N\) 互质的数的个数称为欧拉函数，记为 \(\varphi(N)\)。
性质
欧拉函数性质一：
\(N\) 可以表示为 \(p_{1}^{c_1}p_{2}^{c_2}p_{3}^{c_3}\dots p_{m}^{c_m}\)。
对于 \(N\) 的质因子 \(a\)，\(a\) 的倍数中在 \([1,N]\) 区间内的有 \(a,2a,3a,\dots,(N/a)*a\)，共有 \(N/a\) 个。
对于另一个 \(N\) 的质因子 \(b\),同理，\(b\) 的倍数中在 \([1,N]\) 区间内的有 \(N/b\) 个。
则在 \(1~N\) 中既不是 \(a\) 的倍数又不是 \(b\) 的倍数的个数按理说有 \(N-\frac{N}{a}-\frac{N}{b}\) 个，但 \(b\times a\) 的倍数被减了两次需要加回一次，所以个数是 \(N-\frac{N}{a}-\frac{N}{b}+\frac{N}{b\times a}=N\times (1-\frac{1}{a}-\frac{1}{b}+\frac{1}{a\times b})=n(1-\frac{1}{a})(1-\frac{1}{b})\)。
加以扩深的：\(\varphi(N)=N\times \prod_{质数p\mid N}{} (1-\frac{1}{p})\)
所以求欧拉函数的方法一：质因数分解法
int phi(int n){
int ans=n;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
}
if(n>1)ans=ans/n*(n-1);
return ans;
}