数论函数及定理
积性函数
附 OI Wiki 链接。
定义
对于函数 \(f(x)\)，满足 \(f(1)=1\) 且 \(\forall \gcd(a,b)=1, f(ab)=f(a)f(b)\)。则 \(f(x)\) 是积性函数。
如果对所有 \(a,b\) 都成立，\(f(x)\) 就是完全积性函数。
例子
欧拉函数 \(\varphi(x)\) 是积性函数。
欧拉函数
定义
欧拉函数 \(\varphi(x)\) 等于 $\le x $ 且与 \(x\) 互质的数的个数。比如 \(\varphi(1)=1,\varphi(6)=2\)。
性质和公式
- \(\varphi(x)\) 是积性函数。
- 推论
将 \(n\) 质因数分解，得到 \(n = \sum_{i=1}^s p_i^{c_i},c_i>0\)。
\[\varphi(n) = \prod_{i=1}^s \varphi(p_i^{c_i}) \]积性函数的性质。
- 神秘公式。
不好证，证明鸽掉。
- 引理。
\(p\) 是质数。
\[\varphi(p^k) = p^k - p^{k-1} \]由定义可证。
- 计算用公式。
显然 \(c_i\) 不影响 \(\varphi(n)\)。
\[\begin{aligned} \varphi(n) & = \prod_{i=1}^s \varphi(p_i^{c_i})\\ & = \prod_{i=1}^s p_i^{c_i} - p_i^{c_i-1} \\ & = \prod_{i=1}^s p_i(1-\frac{1}{p_i}) \\ & = n \times \prod_{i=1}^s \frac{p_i-1}{p_i} \end{aligned} \]线性筛求欧拉函数
线性筛的时候我们会求出每个数的最小质因数 \(pri_n\)。
设 \(n' = \frac{n}{pri_n}\)。
-
\(pri_n \mid n'\)。
则 \(n\) 和 \(n'\) 的质因子种类相同，只是 \(n\) 多一个 \(pri_n\) 罢了。
根据欧拉函数的计算用公式，得到 \(\varphi(n) = pri_n \varphi(n')\)。
-
\(pri_n \nmid n'\)。
此时 \(n\) 比 \(n'\) 多一种质因子 \(pri_n\)，数量是多一个，那么有 \(\varphi(n) = (pri_n - 1) \varphi(n')\)。
莫比乌斯函数
定义
莫比乌斯函数 \(\mu(n)\) 定义为：
\[\mu(n) = \begin{cases} 1\\ 0 \ (n 有平方因子)\\ (-1)^k \ k 是 n 的因子个数 \end{cases} \]性质
-
\(\mu(n)\) 是积性函数。
-
最常用性质。
将 \(n\) 质因数分解：\(n = \sum_{i=1}^s p_i^{c_i}\)。
\(\sum_{d \mid n} \mu(d) = \sum_{k=0}^s \binom{s}{k} (-1)^k = (1+(-1))^s = [s=0]\)。
- 神奇的性质。
不会证。
线性筛求莫比乌斯函数
void init_mu() {
mu[1]=1;
rep(i,2,Max) {
if(!vi[i]) mu[i]=-1, p[++p0]=i;
for(int j=1;j<=p0 && i*p[j]<=n;j++) {
vi[i*p[j]]=1;
if(i%p[j]==0) break;
mu[i*p[j]]=-mu[i];
}
}
}
莫比乌斯反演
如果有函数 \(F(n)\) 和 \(f(n)\) 满足：
\[F(n) = \sum_{n \mid d} f(d) \]那么有：
\[f(n) = \sum_{n \mid d} \mu(\frac{d}{n}) F(d) \]不会证，不证。
经验
容斥一下，变成每次询问求 \(O(1)\) 个 \(f(k)=\sum_{i=1}^a \sum_{j=1}^b [\gcd(i,j)=k]\)。
我们知道求 \(F(k)\) 表示 \(i\le a,j\le b,k\mid \gcd(i,j)\) 是好求的，等于 \(\lfloor \frac{a}{k} \rfloor \lfloor \frac{b}{k} \rfloor\)。
然后又有 \(F(k) = \sum_{k \mid d} f(d)\)，根据莫比乌斯反演公式，得到 \(f(n) = \sum_{k\mid d} \mu(\frac{d}{k}) F(d)\)。
\[ans = f(k) = \sum_{k \mid d} \mu(\frac{d}{k}) F(d) = \sum_{t=1}^{\min(\lfloor \frac{a}{k} \rfloor,\lfloor \frac{b}{k} \rfloor)} \mu(t) \lfloor \frac{a}{kt} \rfloor \lfloor \frac{b}{kt} \rfloor \]然后整除分块一下，单次询问 \(O(\sqrt{n})\)。
标签：frac,函数,数论,定理,mid,varphi,mu,sum From： https://www.cnblogs.com/liyixin0514/p/18673826