数论大合集（柿子版）

先引入一些概念：

数论函数：定义域为正整数的函数。
积性函数：如果函数 (f(n)) 满足当 (gcd(n,m)=1) 时 (f(nm)=f(n)f(m))，那么我们称 (f(n)) 为积性函数。
完全积性函数：就是积性函数去掉那个互质的条件。
艾弗森约定：对于布尔型变量 (x)：([x]) 表示 (x) 为真时取 1，为假时取 0。
点积 ((fcdot g)(n)=f(n)g(n))

一些简单的例子：

元函数 (varepsilon(n)=[n=1]) 根据定义，是完全积性的。
幂函数 (id_k(n)=n^k) 根据定义，是完全积性的。
单位函数 (1(n)=id_0(n))。
约数幂函数 (sigma_k(n)=sum_{d|n}d^k)，根据定义是积性的。
欧拉函数 (varphi(n)=sum_{dleq n}[gcd(d,n)=1]) 是积性的，具体形式和证明下叙。
莫比乌斯函数 (mu(n)) 满足 (sum_{d|n}mu(d)=[n=1]=varepsilon(n)) 是积性的，具体形式和证明下叙。

「下叙」
(varphi(n))：我们先将 (n) 素因数分解为标准形式：

[n=sum_{i=1}^m p_i^{k_i} ]

那么我们有容斥形式：

[varphi(n)=n-(n/p_1)-(n/p_2)-cdots+(n/p_1p_2)+cdots ]

然后做简单的乘法分配律就有：

[varphi(n)=nprod_{i=1}^m(1-frac 1{p_i}) ]

于是这个形式显然是积性的。

一个性质：

[sum_{d|n}varphi(d)=n ]

这个的证明可以考虑组合意义。

(mu(n))：自己推一下显然有形式：

[mu(n)= left{ egin{aligned} & 1 & (n=1)\ & 0 & exists d>1Rightarrow d^2|n\ & (-1)^{omega(n)} & otherwise end{aligned} ight. ]

那么显然是积性的。

假设 (f(n)) 和 (g(n)) 是数论函数，那么我们定义它们的狄利克雷卷积（Dirichlet Convolution）为：

[h(n)=(fotimes g)(n)=sum_{d|n} f(d)g(frac nd) ]

一些性质：

狄利克雷卷积满足交换律
狄利克雷卷积满足结合律
如果 (f) 和 (g) 都是积性的，那么 (fotimes g) 也是积性的

一些例子：

[1otimes mu=varepsilon ]

[varphi otimes 1=id_1 ]

[id_kotimes 1=sigma_k ]

[fotimes varepsilon=f ]

一道简单的习题：

求

[sum_{i=1}^nsum_{k|i}f(k)mu(frac ik)mod 10^9+7 ]
的值，其中

[f(n)=sum_{d|n}varphi(d)sigma_0(frac nd) ]
(nleq 10^{10^6})，时限 1s，由于是式子题，请给出严格证明。

sol.

注意到

[sigma_0(n)=sum_{d|n}1=1otimes1 ]

所以

[f=varphiotimes1otimes1=id_1otimes1(=sigma_1) ]

那么回归原式：

[fotimesmu=id_1otimes1otimesmu=id_1 ]

那么原式就等于

[sum_{i=1}^ni=frac{n(n+1)}{2} ]

注意到我们有一个特殊的卷积式：

[muotimes 1=varepsilon ]

那么如果我们知道 (f(n)=sum_{d|n}g(d))，亦即 (f=gotimes 1)，那么根据卷积式以及我们知道的运算律，有

[fotimes mu=gotimes 1otimes mu=g ]

写成常见形式就是：

[f(n)=sum_{d|n}g(d)Leftrightarrow g(n)=sum_{d|n}f(d)mu(frac nd) ]

一些例题：

化简求值：

[sum_{i=1}^nsum_{j=1}^ngcd(i,j) ]
(nleq 10^6)

sol.
这类枚举 gcd 的问题有经典套路：先枚举 gcd，然后

[gcd(i,j)=dRightarrow gcd(frac id,frac jd)=1 ]

试一试

[egin{aligned} = & sum_{d=1}^ndsum_{i=1}^nsum_{j=1}^n[gcd(i,j)=d]\ = & sum_{d=1}^ndsum_{i=1}^{n/d}sum_{j=1}^{n/d}[gcd(i,j)=1]\ end{aligned} ]

然后这里观察一下组合意义：后面两个和号相当于在枚举 (leq n/d) 的数中有多少对互素的，这就是 (2sum_{k=1}^{n/d}varphi(k)-1)，减一是因为 1 和自己只能算一次。

那么就是

[egin{aligned} sum_{d=1}^nd(2sum_{i=1}^{n/d}varphi(i)-1) end{aligned} ]

于是这个可以 (mathcal{O}(n)) 做。

加强版

化简求值：

[sum_{i=1}^nsum_{j=1}^ngcd(i,j) ]
(nleq 10^6)，多组数据 (Tleq 10^4)

sol.

首先我们先拿着之前的柿子化一下：

[=2sum_{d=1}^ndPhi(n/d)-frac{n(n+1)}{2} ]

其中

[Phi(n)=sum_{i=1}^nvarphi(i) ]

这个可以预处理出来。然后呢？

然后我们发现，对于很多的 (d)，(n/d) 的取值都相同。确切来说，最多只有 (mathcal{O}(sqrt n)) 种不同的取值。那么我们可以对于相同的一部分值一起处理（就是前缀和减一减），于是就可以单次 (mathcal{O(sqrt n)}) 做。

for(int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (S(r) - S(l - 1)) * Phi(n / l);
}

另一个加强版

化简求值：

[sum_{i=1}^nsum_{j=1}^mgcd(i,j) ]
(n, mleq 10^6)

sol.

现在就没办法使用 (varphi) 来化简了，怎么做？

首先先假定 (nleq m)，那么按照上面的做法化简：

[egin{aligned} = & sum_{d=1}^ndsum_{i=1}^nsum_{j=1}^m[gcd(i,j)=d]\ = & sum_{d=1}^ndsum_{i=1}^{n/d}sum_{j=1}^{m/d}[gcd(i,j)=1]\ end{aligned} ]

这时候我们注意到后面是一个元函数的形式，于是我们可以将其反演出来：

[egin{aligned} = & sum_{d=1}^ndsum_{i=1}^{n/d}sum_{j=1}^{m/d}sum_{k|i,k|j}mu(k)\ = & sum_{d=1}^ndsum_{k=1}^{n/d}mu(k)sum_{i=1}^{n/(kd)}sum_{j=1}^{m/(kd)}1\ = & sum_{d=1}^ndsum_{k=1}^{n/d}mu(k)lfloorfrac{n}{kd} floorlfloorfrac{m}{kd} floor\ end{aligned} ]

现在复杂度就是调和级数一个 (log) 了，但是我们再化简试试？

我们令 (T=kd)，然后：

[egin{aligned} = & sum_{T=1}^nlfloorfrac{n}{T} floorlfloorfrac{m}{T} floorsum_{d|T}dmu(frac Td)\ end{aligned} ]

然后注意到后面这个东西就是 (varphi)，于是可以线性筛，总复杂度 (mathcal{O(n)})

究极加强版

化简求值：

[sum_{i=1}^nsum_{j=1}^mgcd(i,j) ]
(n, mleq 10^6) 多组数据 (Tleq 10^4)

sol.

一样的套路，整除分块即可。

如果你坚持看到了现在那你大概率会发现，数论的很多柿子都需要前缀和，如何快速（亚线性地）求前缀和呢？

我们假定现在要求 (F(n)=sum_{i=1}^nf(i))，那么我们找到它的一个狄利克雷卷积式 (h=fotimes g)，然后我们来考虑 (h) 的前缀和 (H)：

[H(n)=sum_{i=1}^nsum_{d|i}f(d)g(frac id) ]

我们现在交换和号：

[H(n)=sum_{d=1}^ng(d)sum_{i=1}^{n/d}f(i)=sum_{i=1}^ng(i)F(n/i) ]

于是移一移：

[F(n)=frac{1}{g(1)}(H(n)-sum_{i=2}^ng(i)F(n/i)) ]

然后后面的东西可以整除分块递归下去做。复杂度是 (mathcal{O}(n^{3/4}))，如果预处理前 (n^{2/3}) 处的取值并记忆化搜索就是 (mathcal O(n^{2/3}))，而且记忆化搜索后的复杂度是和调用次数无关的（就是说即使在整除分块内部使用也不影响复杂度）。

来丶例题

第五次加强

化简求值：

[sum_{i=1}^nsum_{j=1}^mgcd(i,j) ]
(n, mleq 10^{10})

sol.

还是上面的函数，令 (f(n)=varphi(n))，(g(n)=1)，于是 (h=id_1)。于是可以做了。