引言
自 Mr.果 讲了 CF1900D 之后,决定复习 n 月之前学习的知识:欧拉函数。
\[\Large{{一、\underline{定义}}} \]\[\scriptsize \mathsf {一切的开始} \]
欧拉函数,即 \(\varphi(x)\)。
\[\varphi(x) = \sum_{i = 1}^{x} [\gcd(x,i) = 1] \]它表示小于等于 \(x\) 的数中,与 \(x\) 互质的数的个数。
特别的,
-
\(\varphi(1) = 1\);
-
\(\varphi(p) = p - 1\)(\(p\) 为质数);
\[\Large{\mathsf{二、\underline{性质}}} \]\[\scriptsize \mathsf{解题或优化的关键} \]
- \(\varphi(x)\) 为积性函数。
用途: 线性筛法求范围内所有 \(\varphi(x)\)。
- 欧拉反演
一个正整数 \(n\) 可以表示为:
证明
如果 \(\gcd(k, n) = d\),那么
\(\gcd(\dfrac{k}{d},\dfrac{n}{d}) = 1\), \(( k < n )\)。
如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数,那么
\(n = \sum_{i = 1}^n{f(i)}\)。根据上面的证明,我们发现,
\(f(x) = \varphi(\dfrac{n}{x})\),从而
\(n = \sum_{d \mid n}\varphi(\dfrac{n}{d})\)。注意到约数 d 和 \( \dfrac{n}{d}\) 具有对称性,所以上式化为 \(n = \sum_{d \mid n}\varphi(d)\)。\(\tiny (Ctrl\; + \;v \;不要 \%)\)
\[\Large{\mathsf{三、\underline{应用}}} \]\[\scriptsize \mathsf{一些较为基础的套路 or 算法} \]\[\large{\mathsf{1、\underline{线性筛求欧拉函数}}} \]
基本用途:对于要使用多个 \(\varphi(x)\) 的值时,如果一个一个 \(O(\sqrt n)\) 的求,效率将会很慢,而该算法适用于求一定值域范围内的所有欧拉函数值。
Time: \(\text{O}(n)\quad\) **Memory: **\(\text{O}(n)\)
使用性质:欧拉函数是积性函数。
小声BB:所有积性函数都可以用线性筛来求
ll pri[M], tot, phi[M];
bool isp[M];
// pri -> 储存素数(线性筛的基本框架)
// tot -> 素数个数
// isp -> 是否是素数
// phi -> 欧拉函数值
void pre(int Max){// Max -> 上界
for(int i = 1; i <= Max; i ++) isp[i] = 1;
isp[1] = 0;
phi[1] = 1;//phi(1) = 1
for(int i = 2; i <= Max; i ++){
if(isp[i]){
pri[++ tot] = i;
phi[i] = i - 1;//除了1以外,所有小于等于质数的数都与质数互质
}
for(int j = 1;j <= tot && i * pri[j] <= Max;j ++){
isp[i * pri[j]] = 0;
if(i % pri[j]) phi[i * pri[j]] = phi[i] * phi[pri[j]];//积性函数的性质
else{
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}
\[\large{\mathsf{2、\underline{gcd 求和}}}
\]标签:Phi,函数,数论,varphi,mathsf,underline,欧拉,gcd From: https://www.cnblogs.com/Ice-lift/p/17967515额,我也不会证,看看 dalao 的博客吧