1. Miller-Rabin
Miller-Rabin 是一种接受随机性的正确性较高的素数检验方法，它有一定概率将合数判断为素数，但不会将素数判断为合数。
其基本判定思路是，检测素数都具有但合数不具有的特殊性质，如众所周知的费马小定理 \(x^{p-1}\equiv 1\pmod p\)。
1.1 费马素性检验
费马小定理的逆定理：\(x^{p-1}\equiv 1\pmod p \to p\in Prime\) 并不恒成立，例如当 \(x=2,p=341=11*31\)，有 \(2^{340}\equiv 1\pmod {341}\)，我们称这一类通过费马素性检测的合数为伪素数，其中 \(341\) 是最小的伪素数。
我们可以多随机几个 \(x\) 进行检测，全部通过才为素数。但是有一类卡迈克尔数 \(y\)，满足任意 \(x\perp y,x^{y-1}\equiv 1\pmod y\)，这样我们就很难随机出排出他们的答案。（即使这一类数在 \(10^8\) 内只有 \(255\) 个）
1.2 二次探测定理
根据二次剩余，我们有 \(x^2\equiv 1\pmod p\)，有解当且仅当 \(x=\pm1\pmod p\)。这启发我们用于改进朴素的费马素性检测。
我们先随便找一个素数作为底数 \(a\)，检测 \(a^{p-1}\)，因为 \(p\ne 2\)，所以可以不断除以 \(2\)，直到得到一个 \(p\) 为奇数，由二次探测定理可知这个过程中相当于不断开根号，所得到的结果一定是 \(\pm 1\)，如果不是，则一定是合数。我们一直检测到 \(p\) 为奇数或者 \(0\) 即可。
如果我们选择前 \(12\) 个质数可以检测所有在 \(2^{78}\) 内的质数和合数，具体的可见 [OEIS](A014233 - OEIS)，复杂度 \(O(k\log^2 )\)，\(k=12\)。
2. 积性函数与狄利克雷卷积
积性函数：满足 \(f(ab)=f(a)f(b),a\perp b\)，有拓展：\(f(\prod p_i^{c_i})=\prod f(p_i^{c_i})\)。
完全积性函数：不要求互质。
常见的积性函数：
- 单位函数 \(\epsilon (n)=[n=1]\)。当且仅当 \(n=1\) 取值为 \(1\)，它是完全积性函数。
- 常数函数 \(I(n)=1\)。完全积性。
- 恒等函数 \(id(n)=n\)，完全积性。
- 约数函数 \(\sigma _k(n)=\sum\limits_{d|n}d^k\)，当 \(k=0\) 时 \(\sigma_0(n)\) 为约数个数 \(d(n)\)，当 \(k=1\) 时 \(\sigma_1(n)\) 为约数和。
- 欧拉函数 \(\varphi(n)=\sum [i\perp n]\)，即与 \(n\) 互质的数的个数。
- 莫比乌斯函数 \(\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & \exists d > 1, d ^ 2\mid n \\ (-1) ^ {\omega(n)} & \mathrm{otherwise} \end{cases}\)
另外的，还有加性函数 \(f(ab)=f(a)+f(b),a\perp b\)，例如：本质不同因子个数函数 \(\omega(n)=\sum\limits_{p\in P}[p|n]\)，近似可认为 \(\omega(n)=\lg n\)。
狄利克雷卷积：
\[f*g=h,h_i=\sum_{d|i} f_d\cdot g_{i/d} \]狄利克雷前缀和：给定 \(a_n\)，求 \(b_n=\sum\limits_{i|n}a_i\)。
实际就是数论意义上的高维前缀和，将每个素数作为维度。复杂度 \(O(n\log\log n)\)。
for(int i=1;i<=cnt;i++) {
for(int j=1;j<=n&&prime[i]*j<=n;j++) {
a[prime[i]*j]+=a[j];
}
}
卷积恒等式：
-
\(f*\epsilon=f\)。
-
\(\varphi*I=id\iff \sum\limits_d \varphi(d)=n\)
-
\(\mu*I=\epsilon\)
- \[n=\prod p_i^{k_i},n'=\prod p_i \\ \sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^k\binom{k}{i}(-1)^i=(1-1)^k=[n=1]=\epsilon \]
-
\(\mu * id =\varphi\)
-
\(g=f*I\iff f=g*\mu\)。
3. 数论分块
\[\sum_{i=1}^nf(i)g(\lfloor\frac{n}{i}\rfloor) \]前提：\(f\) 的前缀和可快速计算。
感性认知：使得 \(\lfloor\frac{n}{i}\rfloor=k\) 的正整数 \(i\) 范围为 \((\lfloor\frac{n}{k+1}\rfloor,\lfloor\frac{n}{k}\rfloor]\)。
结论1：对于任意 \(i\in[1,n]\)，不同的 \(\lfloor\frac{n}{i}\rfloor\) 只有 \(2\sqrt n\) 个。
我们枚举整除值 \(d\)，求出最小和最大的 \(i\) 使得满足条件，分别记作 \(l,r\)，都可以通过感性认知算。那么原式可写作 \(\sum\limits_{d}g(d)\sum\limits_{i=l}^rf(i)\)，后者前缀和计算。
如何跳过极长的等价 \(i\) 的连续段，\(r=(n/(n/l))\)，均为下取整。
转换
\[\begin{aligned} \sum_{i=1}^n k\bmod i &= \sum_{i=1}^n k-\lfloor\frac{k}{i}\rfloor \times i \\ &=nk-\sum_{i=1}^n \lfloor\frac{k}{i}\rfloor\times i \end{aligned} \]后面再用等差数列求和。
例题
P2260 [清华集训2012] 模积和
\[\begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^m(n\bmod i)\times(m\bmod j),i\ne j \\ &=\sum_{i=1}^n\sum_{j=1}^m(n-) \end{aligned} \]P3579 [POI2014] PAN-Solar Panels
4.莫比乌斯反演
\[[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d) \\ \varphi(n)=\sum_{d|n}d\cdot \mu(\frac{n}{d}) \]常见技巧
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]&= \sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d) \\ &=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\mu(d) \\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \end{aligned} \tag1 \]神秘技巧
\[d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\tag1 \\ \]证明（1）：因为左右两边都是积性函数，所以只需要考虑只有一个质因子的情况即可，设 \(ij=p^k\)，其中 \(i=p^{k_1},j=p^{k-k_1}\)，那么 \(d(ij)=k_1+1\)，考虑等号右边，\(\gcd=1\) 要求了两个数至少有一个为 \(1\)，若 \(i=1\) 有 \(k-k_1+1\) 的贡献，\(j=1\) 有 \(k_1+1\) 的贡献，再减去算重的两个都是 \(1\) 的情况，最终答案 \(k+1\)。应用在[SDOI2015] 约数个数和。
\[\sigma_1(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] \frac{i\cdot x}{y}\tag2 \]入门例题
[HAOI2011] Problem b
求 \(\gcd(x,y)=k,x\in[a,b],y\in[c,d]\) 的个数。
先二维差分转换为下界为 \(1\) 的情况处理：
\[\begin{aligned} \sum_{x\le n}\sum_{y\le m}[\gcd(x,y)=k] &=\sum_{x\le n/k}\sum_{y\le m/d}[\gcd(x,y)=1] \\ &=\sum_{x}\sum_y\sum_{d|\gcd(x,y)}\mu(d) \\ &= \sum_{d=1}^{\min(n,m)} \mu(d) \lfloor\frac{n/k}{d}\rfloor\lfloor\frac{m/k}{d}\rfloor \end{aligned} \]然后需要进行整除分块。
P2398 GCD SUM
\[\begin{aligned} \sum_{i}^n\sum_j^n\gcd(i,j) &=\sum_{i}\sum_j\sum_{d|\gcd(i,j)}d[\gcd(i,j)=d] \\ &= \sum_{d|n} d \sum_{i}^{n/d}\sum_j^{n/d}\sum_{e|\gcd(i,j)}\mu(e) \\ &= \sum_{d|n}d\sum_{e|(n/d)}\mu(e)(n/(de))^2 \\ &= \sum_{D=1}^n\sum_d d\times\mu(D/d)\times(n/D)^2 \\ &=\sum_{D=1}^n\varphi(D)\times (n/D)^2 \end{aligned} \]实际上这完全是莫反学傻了，对于 \(id\) 类的求和，我们有欧拉反演：
\[\begin{aligned} \sum_{i}^n\sum_j^n\gcd(i,j) &=\sum_{i}^n\sum_j^n \sum_{d|\gcd(i,j)}\varphi(d) \\ &=\sum_d \varphi(d)\times (n/d)^2 \end{aligned} \]P1891 疯狂 LCM
\[\begin{aligned} \sum _{i=1}^n \mathrm{lcm}(i,n)&=\sum_{i=1}^n\frac{i\times n}{\gcd(i,n)} \\ &=n\sum_{i=1}^n\sum_{d|\gcd(i,n) }\frac{i}{d}[\gcd(i,n)=d] \\ &=n\sum_{d|n}\sum_{i=1}^{n/d}{i}[\gcd(i,n/d)=1] \\ &=n\sum_{d|n}f(n/d) \\ f(x)=\sum_{i=1}^x i [gcd(i,x)=1] &=\sum_{i=1}^xi\sum_{d|\gcd(i,x)}\mu(d) \\ &=\sum_{d|x}\mu(d)\sum_{i=kd} i \\ &=\sum_{d|x}\mu(d)\frac{(d+x)(x/d)}{2} \\ &=\sum_{d|x}\mu(d) \frac{x}{2}+\frac{x^2}{2d} \\ &=\frac{x}{2}\sum_{d|x}\mu(d)(1+\frac{x}{d}) \\ &=\frac{x}{2}\mu*1+\mu *id \\ &=\frac{x}{2}\mu*1+\mu*1*\varphi \\ &= \frac{x}{2}(\epsilon+\varphi) \\ \end{aligned} \]至此，可以做到 \(O(T\sqrt n)\) 求，继续展开可以做到 \(O(n)\)：
\[ans=n\sum_{d|n}\frac{n/d}{2}([d=n]+\varphi(n/d)) \\ =\frac{1}{2}\sum_{d|n}(n/d)\times\varphi(n/d)+\frac{n}{2} \]可以线性筛出 \(\varphi\times id\)。因为两个积性函数相乘仍然是积性函数。注意这里不是卷积。
当然直接 \(O(n\ln )\) 暴力求也可以。
中等例题
P2257 YY的GCD
\[\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)\in P]&=\sum_p\sum_i\sum_j[\gcd(i,j)=p] \\ &=\sum_{p}\sum_{d=1}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor \end{aligned} \]推不动了，仔细观察，一个常见套路是，如果分母上有两项，则将他们的乘积设出来，令 \(T=pd\)。
\[\begin{aligned} \sum_{p}\sum_{d=1}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor &=\sum_{T}\sum_{d=1}\mu(d)\frac{n}{T}\frac{m}{T} \\ &=\sum_{T}\frac{n}{T}\frac{m}{T}\sum_{p|T} \mu(\frac{T}{p}) \\ &=\sum_{T}\frac{n}{T}\frac{m}{T}f(T) \end{aligned} \]如果我们能求出 \(f\) 的前缀和，那么就可以直接整数分块做。
考虑直接暴力算 \(f\)，素数个数是 \(O(\frac{n}{\ln n})\) 的，调和级数是 \(O(\ln n)\) 的，所以我们暴力就是 \(O(n)\) 的。
P3327 [SDOI2015] 约数个数和
根据神秘 trick，我们有：
\[\begin{aligned} d(ij)&=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1] \\ ans&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|\gcd(x,y)}\mu(d) \\ &=\sum_{d}\mu(d)\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor \frac{m}{y}\rfloor[\gcd(x,y)=d] \\ &=\sum_d\mu(d)\sum_{x=1}^{n/d}\sum_{y=1}^{m/d}\lfloor\frac{n}{dx}\rfloor\lfloor \frac{m}{dy}\rfloor \\ &=\sum_{d=1}\mu(d)(\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dx}\rfloor)(\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor \frac{m}{dy}\rfloor) \\ \end{aligned} \]至此，可以整除分块在 \(O(\sqrt n)\) 内算出答案。
P1829 [国家集训队] Crash的数字表格
\[\begin{aligned} \sum_{i=1}^n\sum _{j=1}^m lcm(i,j) &=\sum_{i=1}^n\sum_{j=1}^m \frac{ij}{\gcd(i,j)} \\ &= \sum_{i=1}^n\sum_{j=1}^m \sum_{d} \frac{ij}{d}[\gcd(i,j)=d] \\ &= \sum_{d} \sum_{i=1}^{n/d}\sum_{j=1}^{m/d} ijd [\gcd(i,j)=1] \\ &= \sum_{d} \sum_{i=1}^{n/d}\sum_{j=1}^{m/d} ijd \sum_{t|\gcd(i,j)} \mu(t) \\ &= \sum_{d=1} d \sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ij\sum_{t|gcd(i,j)}\mu(t) \\ &= \sum_{d=1} d \times f(n/d,m/d) \\ f(n,m) &=\sum_{i=1}^n\sum_{j=1}^m i j \sum_{t|\gcd(i,j)}\mu(t) \\ &= \sum_{t=1} \mu(t)\sum_{i=1}^{n/t}\sum_{j=1}^{m/t} (ijt^2) \\ &=\sum_{t=1}\mu(t)t^2 \times (\sum_{i=1}^{n/t} i)( \sum_{j=1}^{m/t} j) \\ &=\sum_{t=1}\mu(t)t^2\times(1+n/t)(n/t)/2\times (1+m/t)(m/t)/2 \end{aligned} \]发现两者的最后一部都可以数论分块求解，故总复杂度 \(O(\sqrt n \times \sqrt n)=O(n)\)。
P3704 [SDOI2017] 数字表格
\[\begin{aligned} \prod _{i=1}^n\prod_{j=1}^mf_{\gcd(i,j)} &=\prod _{d=1}^{min(n,m)}f(d)\prod _{i=1}^n\prod_{j=1}^m [\gcd(i,j)=d] \\ &= \prod_{d=1}f(d)^{g(d)} \\ g(d)&=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d] \\ &=\sum_{t=1}^{\min(n,m)/d}\mu(t) \lfloor\frac{n}{td}\rfloor\lfloor\frac{m}{td}\rfloor \\ &=\sum_T\mu(T/d)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor \\ T&=td\\ ans&=\prod_{d=1}f(d)^{\sum \mu(T/d)n/Tm/T} \ \\ &=\prod _{d=1}(\prod _{T|d}f(d)^{\mu(\frac{T}{d})})^{\frac{n}{T}\times\frac{m}{T}} \end{aligned} \]其中，\(\prod\limits_{T|d} f(d)^{\mu(\frac{T}{d})}\) 可以调和级数预处理，复杂度 \(O(n\ln n)\)，询问可以直接整除分块。总复杂度 \(O(n\ln n+T\sqrt n \log n)\)。
标签：lfloor,筛子,frac,gcd,sum,莫反,mu,rfloor From： https://www.cnblogs.com/AK-IOI/p/18385592