前置知识

线性筛
四则运算
常见的积性函数

数论函数

定义在正整数集上的实值或复值函数

一般可视作定义域为正整数，值域为整数的函数

积性函数

对于一个数论函数$f$，若当$(a,b)=1$时，$f(ab)=f(a)f(b)$，则称其为积性函数

完全积性函数

对于一个数论函数$f$，若$f(ab)=f(a)f(b)$，则称其为完全积性函数

莫比乌斯函数

$$
\mu(n) =
\begin{cases}
1 \qquad &n=1 \\
(-1)^k \qquad &n=\Pi_{i=1}^{k} p_i \\
0 \qquad &\text{otherwise}
\end{cases}
$$

线性筛莫比乌斯函数

假设当前枚举到了$i$和素数$p$

若$i$是素数

$\mu(i)=-1$

若$p \nmid i$

$\mu(i \times p)=\mu(i)\mu(p)=-\mu(i)$

若$p \mid i$

$\mu(i \times p)=\mu(\frac{i}{p} \times p^2)=0$

狄利克雷卷积

定义数论函数$f$和$g$的狄利克雷卷积为
$$
h(n)=(f \times g)(n)=\sum_{d \mid n}f(d)g(\frac{n}{d})
$$

性质

结合律

$(f \times g) \times h=f \times (g \times h)$

交换律

$f \times g=g \times f$

存在单位元

$f \times \epsilon = \epsilon \times f = f$

传递性

若$f,g$是积性函数，则$f \times g$也是积性函数

若$g$和$f \times g$是积性函数，则$f$也是积性函数

若$f \times \mu$是积性函数，则$f$是积性函数

混合积

若$g$是完全积性函数，且$h=f \times g$，则$f = h \times (\mu \cdot g)$

即
$$
h(n)=\sum_{d \mid n}f(n)g(\frac{n}{d}) \Rightarrow f(n)=\sum_{d \mid n}h(n) \mu(\frac{n}{d})g(\frac{n}{d})
$$

常用变换

$\mu \times 1 = \epsilon$

$\phi \times 1 = id$

$\mu \times id = \phi$

$\sigma_0(ij)=\sum_{x \mid i}\sum_{y \mid j}\epsilon((x,y))$

$\sigma_1(ij)=\sum_{x \mid i}\sum_{y \mid j}\frac{xj}{y}\epsilon((x,y))$

证明

$\mu \times 1 = \epsilon$

证明略
$\phi \times 1 = id$

$$
\begin{align}
\sum_{d \mid n}\phi(d)
&=\sum_{d \mid n}\sum_{i=1}^{d}\epsilon((i,d)) \\
&=\sum_{d \mid n}\sum_{i=1}^{d}\sum_{d’ \mid (i,d)}\mu(d’) \\
&=\sum_{d \mid n}\sum_{d’=1 \wedge d’ \mid d}^{d} \mu(d’)\sum_{i=1 \wedge d’ \mid i}^{d}1 \\
&=\sum_{d \mid n}\sum_{d’ \mid d} \mu(d’) \frac{d}{d’} \\
&=\sum_{d \mid n}\sum_{d’ \mid d} \mu(\frac{d}{d’}) d’ \\
&=\sum_{d’ \mid n}d’\sum_{d \mid n \wedge d’ \mid d} \mu(\frac{d}{d’}) \\
&=\sum_{d’ \mid n}d’\sum_{d \mid \frac{n}{d’}} \mu(d) \\
&=\sum_{d’ \mid n}d’ \epsilon(\frac{n}{d’}) \\
&=n
\end{align}
$$
$\mu \times id = \phi$

$$
\begin{align}
\phi(n)
&=\sum_{i=1}^{n} \epsilon((i,n)) \\
&=\sum_{i=1}^{n}\sum_{d \mid (i,n)}\mu(d) \\
&=\sum_{d=1 \wedge d \mid n}^{n}\mu(d)\sum_{i=1 \wedge d \mid i}^{n}1 \\
&=\sum_{d \mid n}\mu(d)\frac{n}{d} \\
&=(\mu \times id)(n)
\end{align}
$$
$\sigma_0(ij)=\sum_{x \mid i}\sum_{y \mid j}\epsilon((x,y))$

证明略
$\sigma_1(ij)=\sum_{x \mid i}\sum_{y \mid j}\frac{xj}{y}\epsilon((x,y))$

证明略

莫比乌斯反演

对于数论函数$f,g$，若有$f = g \times 1$，则有$g = f \times \mu$

证明

$$
\begin{align}
f = g \times 1 \Rightarrow &f \times \mu = g \times 1 \times \mu \\
\Rightarrow& f \times \mu = g \times 1 \times \mu \\
\Rightarrow& f \times \mu = g \times (1 \times \mu) \\
\Rightarrow& f \times \mu = g \times \epsilon \\
\Rightarrow& g = f \times \mu
\end{align}
$$

计算技巧，不仅仅是交换求和号

贡献独立，各自算完后再合并

$$
\sum_{i=1}^{n}\sum_{j=1}^{m}f(i)g(j)=(\sum_{i=1}^{n}f(i))(\sum_{j=1}^{m}g(j))
$$

正难则反，统计贡献

$$
\begin{align}
\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid (i,j)}f(d)
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid i \wedge d \mid j}f(d) \\
&=\sum_{d=1}^{n}f(d)\sum_{i=1 \wedge d \mid i}^{n}\sum_{j=1 \wedge d \mid j}^{m}1 \\
&=\sum_{d=1}^{n}f(d)(\sum_{i=1 \wedge d \mid i}^{n} 1 ) (\sum_{j=1 \wedge d \mid j}^{m}1) \\
&=\sum_{d=1}^{n}f(d) \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor
\end{align}
$$

变量替换，枚举乘积

$$
\begin{align}
\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^k
&=\sum_{d=1}^{\min(n,m)}d^k\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=d] \\
&=\sum_{d=1}^{\min(n,m)}d^k \sum_{d’=1}^{\lfloor \frac{\min(n,m)}{d} \rfloor}\mu(d’)\lfloor \frac{n}{dd’} \rfloor \lfloor \frac{m}{dd’} \rfloor \\
&=\sum_{T=1}^{\min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} d^k \mu(\frac{T}{d}) \\
&=\sum_{T=1}^{\min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor f(T) \\
f(T) = \sum_{d \mid T} d^k \mu(\frac{T}{d})
\end{align}
$$

取整常识

$\lfloor \frac{n}{x} \rfloor$的取值只有$\sqrt n$种

$\left\lfloor \frac{\lfloor \frac{n}{a} \rfloor}{b} \right\rfloor=\lfloor \frac{n}{ab} \rfloor=\left\lfloor \frac{\lfloor \frac{n}{b} \rfloor}{a} \right\rfloor$

$\left\lceil \frac{\lceil \frac{n}{a} \rceil}{b} \right\rceil=\lceil \frac{n}{ab} \rceil=\left\lceil \frac{\lceil \frac{n}{b} \rceil}{a} \right\rceil$

数论分块

若要计算$f(n)=\sum_{i=1}^{n}i \lfloor \frac{n}{i} \rfloor$

直接计算是$O(n)$的，但$\lfloor \frac{n}{i} \rfloor$的取值只有$\sqrt n$种，不妨将取值相同的同时处理

即找一个最大的$j$，使得$\lfloor \frac{n}{i} \rfloor \le \lfloor \frac{n}{j} \rfloor$
$$
\begin{align}
\lfloor \frac{n}{i} \rfloor \le \lfloor \frac{n}{j} \rfloor \le \frac{n}{j}
\Rightarrow &j \le \frac{n}{\lfloor \frac{n}{i} \rfloor} \\
\Rightarrow &j \le \left\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \right\rfloor
\end{align}
$$

一般的，对于计算$h(n)=\sum_{i=1}^{n}f(i)g(\lfloor \frac{n}{i} \rfloor)$，只需要可以快速计算$f$的前缀和即可用数论分块来快速计算

代码实现

ll F(int n) {
    ll ans = 0;
    for(int i = 1, j = 1 ; i <= n ; i = j + 1) {
        j = n / (n / i);
        ans += (sumf(j) - sumf(i - 1)) * g(n / i);
    } 
    return ans;
}

做题技巧

先写暴力，再写正解

如果做不到$O(\sqrt n)$，$O(n)$也可以（骗部分分）

如果RE/TLE，多半是递归/循环挂了

如果div 0，多半是数论分块挂了

将暴力逐步修改为正解，寻找那个部分写挂了

主要注意是不是哪里写了个假的

小心爆long long

套路

写出暴力计算的式子，然后用$\phi$或$\mu$等已知等价关系式进行替换

交换求和号后计算

有时候会遇到枚举三元环之类的奇奇怪怪的技巧

应用

计算$\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=k]$

$$
\begin{align}
n \le m \\
\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=k]
&=\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[(i,j)=1] \\
&=\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d \mid (i,j)}\mu(d) \\
&=\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d \mid i \wedge d \mid j}\mu(d) \\
&=\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d) \sum_{i=1 \wedge d \mid i}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1 \wedge d \mid j}^{\lfloor \frac{m}{k} \rfloor}1 \\
&=\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \\
\end{align}
$$

计算$\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)$

$$
\begin{align}
n \le m \\
\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid (i,j)}\phi(d) \\
&=\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\phi(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor
\end{align}
$$

计算$\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^k$

$$
\begin{align}
n \le m \\
\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^k
&=\sum_{d=1}^{n}d^k\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=d] \\
&=\sum_{d=1}^{n}d^k \sum_{d’=1}^{\lfloor \frac{n}{d} \rfloor}\mu(d’)\lfloor \frac{n}{dd’} \rfloor \lfloor \frac{m}{dd’} \rfloor \\
&=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} d^k \mu(\frac{T}{d}) \\
&=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor f(T) \\
f(T) = \sum_{d \mid T} d^k \mu(\frac{T}{d})
\end{align}
$$

计算$\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_0(ij)$

$$
\begin{align}
n \le m \\
\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_0(ij)
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{a \mid i}\sum_{b \mid j}[(a,b)=1] \\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1] \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid (i,j)}\mu(d) \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d \mid i \wedge d \mid j}\mu(d) \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \\
&=\sum_{d=1}^{n}\mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{id} \rfloor \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor \frac{m}{jd} \rfloor \\
&=\sum_{d=1}^{n}\mu(d)f(\lfloor \frac{n}{d} \rfloor)f(\lfloor \frac{m}{d} \rfloor) \\
f(n)=\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor
\end{align}
$$