7.乘性函数

本章研究定义在整数集合上的一类函数——乘性函数（或 积性函数），它在一个整数上的函数值等于该整数做素数幂分解后，所有素数幂上的函数值之积

我们还研究称为完全数的特殊正整数，这种数与其真因子之和相等；并证明所有偶完全数是由梅森素数生成，其中梅森素数是形如 2 的方幂减 1 的素数

我们还将证明算术函数的和函数来得到函数自身的一些信息

1. 欧拉 \(\phi\) 函数

算术函数：定义在正整数上的函数，称为算术函数

乘性函数(积性函数)：算术函数 f 如果满足任意两个互素的正整数 n 和 m，均有 \(f(mn)=f(m)f(n)\)，那么 f 称为乘性函数或积性函数

完全乘性函数（完全积性函数）：算术函数 f 如果满足任意两个正整数 n 和 m，均有 \(f(mn)=f(m)f(n)\)，那么 f 称为完全乘性函数或完全积性函数

强乘性函数：乘性函数 f 满足 \(f(p^k)=f(p)\)（\(p\in\mathbb P,k\in\mathbb N^+\)），如：\(f(n)=\phi(n)/n\)

如果 f 是乘性函数，对任意正整数 n 有素数幂分解 \(n=\prod\limits_{i=1}^{\omega(n)}p_i^{\alpha_i}\)，那么 \(f(n)=\prod\limits_{i=1}^{\omega(n)}f(p_i^{\alpha_i})\)

p 是素数，当且仅当 \(\phi(p)=p-1\)

证明：

(1) 充分性：\(i=1..p-1\) 均与 p 互质

(2) 必要性(反证)：p 不是素数：若 p=1，那么 \(\phi(p)=1\ne0\)；若 p 为合数，那么 \(\phi(p)\le p-2\)（\(2,\dots,p-1\) 中至少有一个数不与 p 互质）

\(\blacksquare\)

假设 p 是素数，k 是正整数，那么 \(\phi(p^k)=p^k-p^{k-1}\)（\(k\ge1\)）

\(1,\dots,p^k-1\) 的整数之内只有 \(ip\)（\(i=1..p^{k-1}-1\)）不与 \(p^k\) 互质，即 \(\phi(p^k)=(p^k-1)-(p^{k-1}-1)=p^k-p^{k-1}\)

\(\blacksquare\)

\(\phi(x)\) 是乘性的，即 \(\phi(mn)=\phi(m)\phi(n)\)（\((m,n)=1\)）

注：证明参见 p191

\(\phi(n)=\begin{cases}1&n=1\\\prod\limits_{i=1}^{\omega(n)}(p_i^{\alpha_i}-p_i^{\alpha_i-1})=n\prod\limits_{i=1}^{\omega(n)}(1-\frac1{p_i})&n\ge2\end{cases}\)

注：对于任意乘性函数 f，已知 \(f(1),f(p^k)\)，蕴涵 \(f(x)\) 已知

对于任意正整数 \(n\ge3\)，\(\phi(n)\) 是偶数

证明：

\(\forall n\ge2\)，\(\phi(n)=\prod\limits_{i=1}^{\omega(n)}p_i^{\alpha_i-1}(p_i-1)\)

(1) 若 n 拥有偶素数幂，那么对于其中任意一个偶素数 \(p_i\) 都有 \(2|(p_i-1)\)，进而 \(2|\phi(n)\)（蕴涵 \(n\ge3\)）

(2) 若 n 只有奇素数幂，\(2|2^{\alpha_1-1}(2-1)\)，仅当 \(\alpha_1\ge2\)（蕴涵 \(n\ge4\)）

\(\blacksquare\)

假设 f 是算术函数，f 的和函数定义为 n 中所有正因子处的值之和，即：

\(F(x)=\sum\limits_{d|n}f(d)\)

可证 F 也是乘性函数，蕴涵 \(F(n)=F(\prod\limits_{i=1}^{\omega(n)}p_i^{\alpha_i})=\prod\limits_{i=1}^{\omega(n)}F(p_i^{\alpha_i})=\prod\limits_{i=1}^{\omega(n)}\sum\limits_{j=0}^{\alpha_i}f(p_i^j)\)

若 n 是正整数，那么 \(\sum\limits_{d|n}\phi(d)=n\)

证明：

对整数集合 \(\{1,\dots,n\}\) 按照 \((i,n)\) 进行划分，\(C_d\) 类定义为：\(C_d=\{i~|~\forall i=1..n,(i,n)=d\}=\{i~|~\forall i=1..n,(i/d,n/d)=1\}\)（蕴涵 \(d|n\)）；并且满足 \(n=\sum\limits_{d|n}|C_d|\)

而 \(|C_d|=\sum\limits_{i=1}^n[(i/d,n/d)=1]=\sum\limits_{i=1}^{\lfloor n/d\rfloor}[(i,n/d)=1]=\phi(n/d)\) （第二个等式是由于 \(d|i\)，所以枚举 d 的倍数，于是 \(i'/d=i\)）

于是 \(n=\sum\limits_{d|n}\phi(n/d)\)

注：也可以通过和函数的性质（乘性函数）来证明

\(\blacksquare\)

算术函数 f 和 g 的狄利克雷积为 \((f*g)(n)=\sum\limits_{d|n}f(d)g(n/d)\)

性质：

1. 交换律 \(f*g=g*f\)，结合律 \((f*g)*h=f*(g*h)\)

2. 若 f 和 g 是乘性函数，那么 \(f*g\) 也是乘性函数

3. 若 f 和 g 是算术函数，\(F=f*g\)，那么 \(f=F*g^{-1}\)

推论：

(1) 若 \(h=f*g\)，那么 \((f*g)(p^k)=\sum\limits_{i=0}^kf(p^i)g(p^{k-i})\)，\((f*g)(n)=\prod\limits_{i=1}^{\omega(n)}\sum\limits_{j=0}^{\alpha_i}f(p_i^j)g(p_i^{\alpha_i-j})\)

(2) \((\mu*I_k)(p^t)=p^{k(t-1)}(p^k-1)\)，\((\mu*I_k)(n)=\phi^k\prod\limits_{i=1}^{\omega(n)}\frac{p_i^k-1}{(p_i-1)^k}\)

证明：

(1) 令 \(h=f*g\)，有 \(h(p^k)=\sum\limits_{d|p^k}f(d)g(p^k/d)=\sum\limits_{i=0}^kf(p^i)g(p^{k-i})\)

\(h(n)=\prod\limits_{i=1}^{\omega(n)}h(p_i^{\alpha_i})=\prod\limits_{i=1}^{\omega(n)}\sum\limits_{j=0}^{\alpha_i}f(p_i^j)g(p_i^{\alpha_i-j})\)

(2) \((\mu*I_k)(p^t)=\sum\limits_{i=0}^t\mu(p^i)I_k(p^{t-i})=I_k(p^{t})-I_k(p^{t-1})=p^{kt}-p^{k(t-1)}=p^{k(t-1)}(p^k-1)\)

\(\blacksquare\)

(1) 幂函数：\(I_k(n)=n^k\)

(2) 狄利克雷单位元 \(\iota(n)=\begin{cases}1&n=1\\0&n\ge2\end{cases}=[n=1]\)（乘性）

性质：\(\iota*f=f*\iota=f\)

狄利克雷逆元：\(f^{-1}(1)=1\)，当且仅当 \(f^{-1}\) 是算术函数 f 的逆函数，即 \(f^{-1}*f=f*f^{-1}=\iota\)

(3) 刘维尔函数：\(\lambda(n)=\begin{cases}1&n=1\\(-1)^{\sum\limits_{i=1}^{\omega(n)}\alpha_i}&n\ge2\end{cases}\)（完全乘性）

性质：\(\sum\limits_{d|n}\lambda(d)=\begin{cases}0&n不是完全平方数\\1&n是完全平方数\end{cases}\)；n 是完全平方数，当且仅当 \(\forall i=1..\omega(n),2|\alpha_i\)

加性函数：若对所有互素的正整数 m 和 n 满足 \(f(mn)=f(m)+f(n)\)，那么 f 称为加性函数

完全加性函数：若对所有正整数 m 和 n 满足 \(f(mn)=f(m)+f(n)\)，那么 f 称为完全加性函数（如：\(f(n)=\log n\)）

2. 因子和与因子个数

因子和函数：整数 n 的所有正因子之和，定义为 \(\sigma(n)=\sum\limits_{d|n}d\)

因子个数函数：正整数 n 的所有正因子个数，定义为 \(\tau(n)=\sum\limits_{d|n}1\)

若 f 是乘性函数，那么 f 的和函数 F 也是乘性函数

推论：\(\sigma(n),\tau(n)\) 也是乘性函数

证明：

\(F(mn)=\sum\limits_{d|mn}f(d)=\sum\limits_{d_1|m,d_2|n}f(d_1d_2)=\sum\limits_{d_1|m,d_2|n}f(d_1)f(d_2)=\sum\limits_{d_1|m}f(d_1)\sum\limits_{d_2|n}f(d_2)=F(d_1)F(d_2)\)

\(\blacksquare\)

\(\sigma(p^k)=\sum\limits_{i=0}^kp^i=\frac{p^{k+1}-1}{p-1}\)，\(\tau(p^k)=\sum\limits_{i=0}^k1=k+1\)

\(\sigma(n)=\prod\limits_{i=1}^{\omega(n)}\frac{p_i^{\alpha_i+1}-1}{p_i-1}\)，\(\tau(n)=\prod\limits_{i=1}^{\omega(n)}(\alpha_i+1)\)

3. 完全数，梅森素数

n 称为完全数，如果 n 是一个正整数且满足 \(\sigma(n)=2n\)

注：\(10^6\) 以内只有 4 个完全数：\(6,2,496,8128\)

正整数 n 是偶完全数，当且仅当 \(n=2^{k-1}(2^k-1)\)（其中 \(k\ge2\)，且 \(2^k-1\) 是素数）

证明：

必要性：

\(\sigma(2^{k-1})=\frac{2^k-1}{2-1}=2^k-1,\sigma(2^k-1)=\frac{(2^k-1)^2-1}{(2^k-1)-1}=\frac{2^{2k}-2^{k+1}}{2^k-2}=2^k\)

（其中 \(2^k-1\) 是质数）

由于 \(2^{k-1}\) 与 \(2^k-1\) 的公共质因子，所以两者互质，

那么 \(\sigma(n)=\sigma(2^{k-1}(2^k-1))=\sigma(2^{k-1})\sigma(2^k-1)=(2^k-1)2^k=(2^k-1)2^{k-1}\cdot 2=2n\)

充分性：

偶数 n 可以表示为 \(n=2^st\)（\(s,t\in\mathbb N^+\)，\(2\nmid t\)）

\(\sigma(n)=\sigma(2^st)=\sigma(2^s)\sigma(t)=(2^{s+1}-1)\sigma(t)\) (1)

由于 n 是完全数，有 \(\sigma(n)=2n=2^{s+1}t\) (2)

根据 (1) 和 (2) 有 \((2^{s+1}-1)\sigma(t)=2^{s+1}t\)

其中 \((2^{s+1}-1,2^{s+1})=1\)，根据引理 3.4（？），有 \(2^{s+1}|\sigma(t)\)，即存在 q 使得 \(\sigma(t)=q2^{s+1}\)，

那么 \((2^{s+1}-1)q=t\)，进而 \(q+t=q2^{s+1}=\sigma(t)\) (3)

结合 (1) 和 (3) 有 \(\sigma(n)=2(2^{s+1}-1)2^s\cdot q\)

要证 \(q=1\)：

若 \(q\ne1\)，那么 t 至少有三个因子：\(1,t,q\)，蕴涵 \(\sigma(t)\ge=1+t+q\)，与式 (3) 矛盾；于是 \(q=1\)

于是 \(t=2^{s+1}-1\)，于是 \(n=2^s(2^{s+1}-1)\)

而 \(\sigma(t)=2^{s+1}=t+1\)，于是 \(t=2^{s+1}-1\) 是质数

\(\blacksquare\)

假设 k 是正整数，若 \(2^k-1\) 是素数，那么 k 也是素数

证明(逆否)：k 不是素数，那么 \(2^k-1\) 不是素数

(1) 若 \(k=1\)，那么 \(2^k-1=1\)，即 \(2^k-1\) 不是素数

(2) 假设 k 是合数，那么 \(\exists 1<a,b<m\) 使得 \(k=ab\)，

于是 \(2^k-1=2^{ab}-1=(2^a-1)\sum\limits_{i=0}^{a(b-1)}2^i\)，

上式最右侧的两个因子均不小于 2，蕴涵 \(2^k-1\) 至少有 4 个因子

\(\blacksquare\)

梅森数：若 k 是正整数，那么 \(M_k=2^k-1\) 称为第 k 个梅森数

梅森素数：若 \(M_p=2^p-1\) 是素数，那么 \(M_p\) 称为梅森素数（蕴涵 p 是素数）

若 p 是奇素数，那么梅森素数 \(M_p\) 的因子均形如 \(2kp+1\)（\(k\in\mathbb N^+\)）

4. 莫比乌斯反演

假设 \(F(n)=\sum\limits_{d|n}f(d)\)

经过观察假设 \(f(n)=\sum\limits_{d|n}\mu(d)F(\frac nd)\)（\(\mu\) 是待定函数）

\(\begin{cases}F(1)=f(1)\\F(p)=f(1)+f(p)\\F(p^2)=f(1)+f(p)+f(p^2)\end{cases}\implies\begin{cases}f(1)=F(1)\\f(p)=F(p)-F(1)\\f(p^2)=F(p^2)-F(p)\end{cases}\implies\begin{cases}\mu(1)=1\\\mu(p)=-1\\\mu(p^2)=0\end{cases}\)

或者，\(F(p^k)=\sum\limits_{i=0}^kf(p^i)\implies\forall k\ge1,f(p^k)=F(p^k)-F(p^{k-1})\)

而 \(\forall k\ge2,f(p^k)=F(p^k)-F(p^{k-1})+0\cdot F(1)\implies\begin{cases}\mu(p^k/p^k)=\mu(1)=1\\\mu(p^k/p^{k-1})=\mu(p)=-1\\\mu(p^k/1)=\mu(p^k)=0\end{cases}\)

假设 \(\mu\) 是乘性函数

于是 \(\forall n\in\mathbb N^+\)，\(\mu(n)=\mu(\prod\limits_{i=1}^kp_i^{\alpha_i})=\prod\limits_{i=1}^k\mu(p_i^{\alpha_i})\)

最后得出莫比乌斯函数的定义：\(\mu(n)=\begin{cases}1&n=1\\(-1)^{\omega(n)}&n=\prod\limits_{i=1}^{\omega(n)}p_i\\0&\exists\alpha_i\ge2\end{cases}\)

Mertens 函数：\(M(n)=\sum\limits_{i=1}^n\mu(i)\)

\(\sum\limits_{d|n}\mu(d)=\begin{cases}1&n=1\\0&n>1\end{cases}=[n=1]\)

证明：

(1) \(\sum\limits_{d|1}\mu(d)=\mu(1)=1\)

(2) \(\forall k\ge1\)，\(\sum\limits_{d|p^k}\mu(d)=\mu(1)+\mu(p)+\sum\limits_{i=2}^k\mu(p^i)=1+(-1)+0=0\)

(3) \(\forall n\ge2\)，\(\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n}\mu(\prod\limits_{i=1}^{k_d}p_{di}^{\alpha_{di}})=\sum\limits_{d|n}\prod\limits_{i=1}^{k_d}\mu(p_{di}^{\alpha_{di}})=\sum\limits_{d|n}\prod\limits_{i=1}^{k_d}0=0\)（其中 \(\alpha_{di}>0\)）

\(\blacksquare\)

假设 f 是算术函数，F 是 f 的和函数，满足 \(F(n)=\sum\limits_{d|n}f(d)\)，

那么对于任意正整数 n，有 \(f(n)=\sum\limits_{d|n}\mu(d)F(n/d)\)

证明：

\(\sum\limits_{d|n}\mu(d)F(n/d)=\sum\limits_{d|n}\mu(d)\sum\limits_{e|(n/d)}f(e)=\sum\limits_{d|n}\sum\limits_{e|(n/d)}\mu(d)f(e)\)

由于 \((d,e)\) 满足 \(d|n,e|(n/d)\)，当且仅当 \(e|n,d|(n/e)\)

于是 \(\sum\limits_{d|n}\mu(d)F(n/d)=\sum\limits_{e|n}\sum\limits_{d|(n/e)}\mu(d)f(e)=\sum\limits_{e|n}f(e)\sum\limits_{d|(n/e)}\mu(d)=\sum\limits_{e|n}f(e)[n/e=1]=f(n)\)

\(\blacksquare\)

(1) \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[(i,j)=k]=\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}[(ik,jk)=k]=\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}[(i,j)=1]\)

\(=\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}\iota((i,j))=\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}\sum\limits_{d|(i,j)}\mu(d)=\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{m/k}\sum\limits_{d=1}^{\min\{n/k,m/k\}}[d|i][d|j]\mu(d)\)

\(=\sum\limits_{d=1}^{\min\{n/k,m/k\}}\mu(d)\sum\limits_{i=1}^{n/k}[d|i]\sum\limits_{j=1}^{m/k}[d|j]=\sum\limits_{d=1}^{\min\{n/k,m/k\}}\mu(d)\lfloor\frac{n/k}d\rfloor\lfloor\frac{m/k}d\rfloor\)

\(\blacksquare\)

(2) 错误解答：

\(\sum\limits_{i=1}^n[i,n]=\sum\limits_{i=1}^n\frac{in}{(i,n)}=\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{in}j\iota((i/j,n/j))=\sum\limits_{j=1}^n\sum\limits_{i=1}^{n/j}in\iota((i,n/j))\)

\(=\sum\limits_{j=1}^n\sum\limits_{i=1}^{n/j}in\sum\limits_{d|(i,n/j)}\mu(d)=\sum\limits_{j=1}^n\sum\limits_{i=1}^{n/j}in\sum\limits_{d=1}^{n/j}[d|i][d|(n/j)]\mu(d)\)

\(=n\sum\limits_{j=1}^n\sum\limits_{d=1}^{n/j}[d|(n/j)]\mu(d)\sum\limits_{i=1}^{n/j}i[d|i]=n\sum\limits_{j=1}^n\sum\limits_{d=1}^{n/j}[d|(n/j)]\mu(d)\sum\limits_{i=1}^{n/(jd)}id\)

\(=n\sum\limits_{j=1}^n\sum\limits_{d=1}^{n/j}[d|(n/j)]\mu(d)dS_1(\lfloor\frac n{jd}\rfloor)=n\sum\limits_{d|n}S_1(n/d)\sum\limits_{e|d}\mu(e)e\)

假设 f 是算术函数，它的和函数为 \(F(n)=\sum\limits_{d|n}f(d)\)，

F 是乘性函数，当且仅当 f 是乘性函数

另：若 \(F=f*\nu\)，其中对于所有正整数 n，\(\nu=1\)，那么 \(f=F*\mu\)；利用此性质证明该定理的充分性

引理：若 d 是 \(mn\) 的一个因子（即 \(d|mn\)），则 \(d_1,d_2\) 满足 \(d=d_1d_2\)，\(d_1|m,d_2|n,(d_1,d_2)=1\)

(1) 充分性：

\(f(mn)=\sum\limits_{d|mn}\mu(d)F(\frac{mn}d)=\sum\limits_{d_1|m,d_2|n}\mu(d_1d_2)F(\frac m{d_1}\frac n{d_2})=\sum\limits_{d_1|m,d_2|n}\mu(d_1)\mu(d_2)F(\frac m{d_1})F(\frac n{d_2})\)

\(=\sum\limits_{d_1|m}\mu(d_1)F(\frac m{d_1})\sum\limits_{d_2|n}\mu(d_2)F(\frac n{d_2})=f(m)f(n)\)

(2) 必要性：

\(F(mn)=\sum\limits_{d|mn}f(d)=\sum\limits_{d_1|m,d_2|n}f(d_1d_2)=\sum\limits_{d_1|m,d_2|n}f(d_1)f(d_2)=\sum\limits_{d_1|m}f(d_1)\sum\limits_{d_2|n}f(d_2)=F(m)F(n)\)

\(\blacksquare\)

1. 乘性函数：\(f(mn)=f(m)f(n)\)，\((m,n)=1\)
2. 完全乘性函数：\(f(mn)=f(m)f(n)\)

乘性函数（因子和，因子个数 均是完全乘性函数）：\(\phi,\sigma_k,\tau,\mu,\iota,I_k\)

1. 欧拉函数：\(\phi(n)=\sum\limits_{i=1}^n[(i,n)=1]\)
   1. \(\forall k\in\mathbb N,\phi(p^k)=p^k-p^{k-1}\)，\(\phi(n)=n\prod\limits_{i=1}^{\omega(n)}(1-\frac1{p_i})\)（另外 \(\phi(p^k)=\phi(p^a)p^{k-a}\)，\(a\le k\)）
   2. \(\sum\limits_{d|n}\phi(d)=n\)（\(\phi*I_0=I_1\)）；\(\forall n\ge3,2|\phi(n)\)
2. 因子和：\(\sigma(n)=\sum\limits_{d|n}d\)
   1. \(\forall k\in\mathbb N,\sigma(p^k)=\sum\limits_{i=0}^kp^i=\frac{p^{k+1}-1}{p-1}\)，\(\sigma(n)=\prod\limits_{i=1}^{\omega(n)}\frac{p_i^{\alpha_i+1}-1}{p_i-1}\)
3. 因子个数：\(\tau(n)=\sum\limits_{d|n}1\)
   1. \(\tau(p^k)=\sum\limits_{i=0}^k1=k+1\)，\(\tau(n)=\prod\limits_{i=1}^{\omega(n)}(\alpha_i+1)\)

4. 莫比乌斯函数：（通过莫比乌斯反演 \(f(n)=\sum\limits_{d|n}\mu(d)f(\frac nd)\) 定义）

   1. \(\mu(p^k)=\begin{cases}1&k=0\\-1&k=1\\0&k\ge2\end{cases}\)，\(\mu(n)=\begin{cases}1&n=1\\(-1)^{\omega(n)}&\forall\alpha_i=1\\0&\exists\alpha_i\ge2\end{cases}\)
   2. \(\sum\limits_{d|n}\mu(d)=[n=1]\)（\(\mu*I_0=\iota\)）；即 \(\mu\) 与 \(I_0\) 互逆

5. 幂函数 && 和函数,部分和：\(I_k(n)=n^k\)，\(\sigma_k(n)=\sum\limits_{d|n}d^k\)，\(S_k(n)=\sum\limits_{i=1}^nI_k(i)=\sum\limits_{i=1}^ni^k\)（\(k\in\mathbb N\)）

   1. \(I_k*I_0=\sigma_k\)，\(\sigma_0=\tau,\sigma_1=\sigma\)
   2. \(I_aI_b=I_{a+b}\)，\(I_kf*I_kg=I_k(f*g)\)，\(I_a*I_{a+b}=I_a\sigma_b\)

\(\phi\to I_1\to\sigma,\iota\to I_0\to\tau\)

(1) 分块技术

数论分块主要任务是计算 \(\sum\limits_{i=1}^nf(\lfloor\frac{n}{i}\rfloor)\)

定义两个序列 \(\{a_n\},\{b_n\}\) 满足：\(a_1=1,b_1=1\)，\(a_i=b_{i-1}+1,b_i=\lfloor\frac{n}{\lfloor n/a_i\rfloor}\rfloor\)（\(i=1..k\)，\(k\le2\sqrt n\)）

\(\sum\limits_{i=1}^nf(\lfloor\frac{n}{i}\rfloor)=\sum\limits_{i=1}^kf(\lfloor\frac{n}{a_i}\rfloor)(b_i-a_i+1)\)（其中 \(k\le2\sqrt n\)）

推论：\(\sum\limits_{i=1}^nf(\lfloor\frac{n}{i}\rfloor)g(i)=\sum\limits_{i=1}^kf(\lfloor\frac{n}{a_i}\rfloor)[\mathsf G(b_i)-\mathsf G(a_i-1)]\)（其中 G 是 g 的部分和：\(\mathsf G(n)=\sum\limits_{i=1}^ng(i)\)）

\(\sum\limits_{i=1}^n\sum\limits_{d|n}f(i,d)=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\lfloor n/d\rfloor}f(id,d)\)

假设 f 已知，构造 g 和 h 满足：\(h=g*f\)

计算卷积的部分和：\(\sum\limits_{i=1}^nh(i)=\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)f(i/d)=\sum\limits_{d=1}^n\sum\limits_{i=1}^{\lfloor n/d\rfloor}g(d)f(i)=\sum\limits_{d=1}^ng(d)\mathsf F(\lfloor n/d\rfloor)\)

于是 \(g(1)\mathsf F(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)\mathsf F(\lfloor n/d\rfloor)=\mathsf H(n)-\sum\limits_{d=2}^ng(d)\mathsf F(\lfloor n/d\rfloor)\)

根据数论分块有：\(\mathsf F(n)=\displaystyle\frac{\mathsf H(n)-\sum\limits_{i=2}^k[\mathsf G(b_i)-\mathsf G(a_i-1)]\mathsf F(\lfloor n/a_i\rfloor)}{g(1)}\)

复杂度：\(T(n)=\sum\limits_{i=2}^{\sqrt n}T(\lfloor n/a_i\rfloor)\)，解得 \(T(n)=\omicron(n^{3/4})\)

若 \(\forall n\le n^{2/3},\mathsf F(n)\) 已知，那么 \(T(n)=O(n^{2/3})\)（允许 \(n\le10^{10}\)）

结论：要快速计算 f 部分和，必须满足：g 和 h 的部分和为常数复杂度，并且 \(h=g*f\)；若 \(n^{2/3}\) 以内的 f 的部分和能线性计算，那么可以加速计算复杂度为 \(O(n^{2/3})\)

注：杜教筛的复杂度是可以均摊的

推论：

1. \(M(n)=1-\sum\limits_{i=2}^nM(\lfloor\frac ni\rfloor)\)
2. \(\Phi(n)=\frac {n(n+1)}2-\sum\limits_{i=2}^n\Phi(\lfloor\frac ni\rfloor)\)

(1) \(\sum\limits_{i=1}^n\sum\limits_{j=1}^nij(i,j)=\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\sum\limits_{k=1}^{(i,j)}k\iota(\frac{(i,j)}k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\sum\limits_{k=1}^{(i,j)}k\iota((i/k,j/k))=\sum\limits_{k=1}^nk^3\sum\limits_{i=1}^{n/k}i\sum\limits_{j=1}^{n/k}j\iota((i,j))\)

\(=\sum\limits_{k=1}^nk^3\sum\limits_{i=1}^{n/k}i\sum\limits_{j=1}^{n/k}j\sum\limits_{d|(i,j)}\mu(d)=\sum\limits_{k=1}^nk^3\sum\limits_{i=1}^{n/k}i\sum\limits_{j=1}^{n/k}j\sum\limits_{d=1}^{n/k}[d|i][d|j]\mu(d)\)

\(=\sum\limits_{k=1}^nk^3\sum\limits_{d=1}^{n/k}\mu(d)\sum\limits_{i=1}^{n/k}i[d|i]\sum\limits_{j=1}^{n/k}j[d|j]=\sum\limits_{k=1}^nk^3\sum\limits_{d=1}^{n/k}\mu(d)\sum\limits_{i=1}^{n/(kd)}di\sum\limits_{j=1}^{n/(kd)}dj\)

\(=\sum\limits_{k=1}^nk^3\sum\limits_{d=1}^{n/k}d^2\mu(d)S_1(\lfloor\frac n{kd}\rfloor)^2=\sum\limits_{k=1}^nk^3\sum\limits_{d=1}^{n/k}d^2\mu(d)S_3(\lfloor\frac n{kd}\rfloor)\)

1. \((f,g)(n)=\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}f(d)g(n/d)\)

2. \((f,g)(n)=\sum\limits_{i=1}^nf(i)\mathsf G(\lfloor n/i\rfloor)=\sum\limits_{i=1}^n\mathsf F(\lfloor n/i\rfloor)g(i)\)

3. \((f,g)(n)=\sum\limits_{k=1}^n\prod\limits_{i=1}^{\omega(k)}\sum\limits_{j=0}^{\alpha_i}f(p_i^j)g(p_i^{\alpha_i-j})\)

\((\iota,\iota)=\iota,(f,\iota)=\mathsf F\)，\((I_k,\iota)=S_k\)