数论结论 总结
小结论
\(1\sim n\) 的因数总共有 \(O(n\log n)\) 个，调和级数证明。
\[\varphi(ij)\varphi(\gcd(i ,j)) = \varphi(i)\varphi(j)\gcd(i, j)
\]
\[d(ij) = \sum_{x | i}\sum_{y | j} [\gcd(x, y) = 1]\\
d(ijk) = \sum_{x | i}\sum_{y | j}\sum_{z | k} [\gcd(x, y) = 1][\gcd(y, z) = 1][\gcd(x, z) = 1]
\]
合理猜测更多乘积时也是有以上规律的。
素数定理
\(\le n\) 的质数个数有 \(\dfrac{n}{\ln n}\) 个左右。
Bertrand假设
\(\forall n\ge 1, \exists p\in[n, 2n]\)。
积性函数万能筛法
对于积性函数 \(f\)，考虑 \(f(p ^ k), p\in \text{Primes}\)，如果可以快速求出这个值，那么对于 \(1\sim n\) 的所有单点值都可以筛出来，因为可以考虑把 \(f(n)\) 拆分为 \(\prod f(p_i^{\alpha i})\) 的形式，只对最小的质因数处理即可。
推式子技巧
- 根号分治
对于形如：
\[\sum_{i = 1}^n S(n / i, i)
\]
的式子，可以考虑根号分治。
- 换元
对于形如：
\[\sum_{i = 1}^n f(i)\sum_{j = 1}^{\frac ni} g(\dfrac n{ij})
\]
的式子可以考虑换元 \(T = ij\)。