---

title: 「学习笔记」数论函数
date: 2017-12-31 23:59:56
笔记

mathjax: true

UPD 2017.12.26 重新学了一发莫比乌斯反演，算是会一些套路了？

UPD 2017-12.28 完结，撒花！

其实数论真的很优美毒，不是吗？

前置技能

定义

数论函数。 定义域为正整数的函数。以下默认所有数都是正整数。

积性函数。 对于所有 $\gcd (a,b) = 1$ ， $f(ab) = f(a)f(b)$ 。一定会满足 $f(1) = 1$。

完全积性函数。 对于 任意 的 $a,b$， $f(ab) = f(a)f(b)$ 。

在实际应用中，用到的大多都是 积性函数。

积性函数的性质

积性。 若 $f,g$ 为积性函数， 那么 $(fg)(n) = f(n)g(n), (\frac f g)(n) = \frac {f(n)} {g(n)}$ 也都是积性函数。

用线性筛求 $[1,n]$ 的积性函数。 令 $n = \prod p _ {i} ^ {k_ i}$ ,那么 $f(n) = \prod f(p _ {i} ^ {k_ i})$ 。

所以在线性筛的时候，有一种方法就是 计算所有 $f(p_i) ^{k_i}$ 再相乘 。

另一种方法是，考虑增加一个最小质因子后的变化。

常见的积性函数及其性质

欧拉函数，积性。 $\varphi(n) = \sum _ {i=1} ^n [\gcd(n,i)=1]$ 表示 $[1,n]$ 中与 $n$ 互质的数的个数。

直接根据欧拉函数的定义就可以得到一些有用的式子。比如：（注意利用 $\gcd(n,i) = \gcd(n,n-i)$，以及 $n=1$ 时少算了一次 ）

$$\sum _ {i=1} ^ n i \cdot [\gcd(n,i)=1] = \frac 1 2 \times (n \cdot \sum _ {i=1} ^{n} [\gcd(n,i)=1] + [n=1]) = \frac {n \cdot \varphi(n) + [n=1]} 2 \tag 1$$

$$\sum _ {i=1} ^ n \sum _ {j=1} ^ n [\gcd (i, j) = 1] =2 \sum _ {i=1} ^n \varphi(i) - 1 \tag {2}$$

莫比乌斯函数，积性。 当 $n$ 含有平方因子 $\mu(n) = 0$ , 否则 $n$ 为 $k$ 个不同的质因子乘积， $\mu(n) = -1 ^{k}$ 。

除数函数，积性。 $\sigma _ {k} (n)$ 表示 $n$ 的所有因数的 $k$ 次幂之和。

特别的，$d(n) = \sigma _ {0} (n)$ ，表示 $n$ 的因数个数。

$\sigma _ {1} (n) = \sigma (n)$ ，表示 $n$ 的所有因数之和。

这个角标在上在下都是等价的！

幂函数，完全积性。 $id _ {k} (n)$ ，表示 $n^k$ 。

特别的， $id _ {0} (n) = 1 (n) = 1$ 。

单位函数，完全积性。 当且仅当 $n=1$ 时， $e(n)=1$ ，否则 $e(n)=0$ 。

Dirichlet卷积

定义

两个数论函数 $f,g$ 的Dirichlet卷积。

$$\large (f \ast g)(n) = \sum _ {d|n} f(d) \times g(\frac n d) \tag{3}$$

性质

定义。 $(f+n)(n) = f(n) + g(n)$ .

交换律。 $f \ast g = g \ast f$

结合律。 $(f \ast g) * h = f \ast (g \ast h)$

分配率。 $f \ast (g + h) = f \ast g + f \ast h$

单位元。 $f \ast e = f$

当 $f,g$ 为积性函数时， $f \ast g$ 也为积性函数。

如果有一个积性函数 $f$ ，则一定存在 $g*f=e$ ， $g$ 就是 $f$ 的Dirichlet逆，也是积性函数。

已知数论函数 $f,g$ ，则可以枚举倍数，在 $O(n \log n)$ 的时间内计算出 $f \ast g$ 。

常见的Dirichlet卷积

一个函数的约数和可以卷上1。

$$d(n) = \sum _ {d|n} 1 \Rightarrow d = 1 \ast 1 \tag{4}$$

$$\sigma (n) = \sum _ {d|n} d \Rightarrow \sigma = d \ast 1 \tag{5}$$

极其重要的，莫比乌斯反演的基础

$$\large \sum _ {d|n} \mu(d) = \sum _ {i=0} ^{k} (-1) ^{i} \times \binom k i = (1-1) ^{k} = e(n) \Longrightarrow e = \mu * 1 \tag{6}$$

另一个常用的卷积。 因为 $\varphi(d)$ 表示与 $n$ 的最大公约数为 $\frac n d$ 的数的个数，它们的和显然为 $n$ 。

$$\large \sum _ {d|n} \varphi (d) = n \Longrightarrow \varphi \ast 1 = id \tag{7}$$

莫比乌斯反演

形式一：因数反演

如果两个数论函数 $f,g$ 满足 $f = g \ast 1$ ，也即

$$\large f(n) = \sum _ {d|n} g(d) \tag{8}$$

那么它们满足 $g = \mu * f$ ，也即

$$\large g(n) = \sum _ {d|n} \mu (d) \times f(\frac n d) \tag {9}$$

考虑证明 $f = g \ast 1 \Leftrightarrow g = \mu \ast f$

已知

$$\large f = g \ast 1$$

两边都卷上 $\mu$ ,可得

$$\large f \ast \mu = g \ast \mu \ast 1 = g \ast e = g$$

已知

$$\large f \ast \mu = g$$

两边都卷上 $1$ ，可得

$$\large g \ast 1 = f \ast \mu \ast 1 = f \ast e = f$$

本质？ $1$ 与 $\mu$ 在 Dirichlet卷积意义下互为逆元。

形式二：倍数反演

这就不是Dirichlet卷积了，不过也是对的。

$$\large g(n) = \sum _ {n|d} f(d) \Longrightarrow f(n) \sum _ {n|d} \mu( \frac d n) g(d) \tag {10}$$

变换技巧

一些基本套路，多推推就熟练了。

1.枚举 $\gcd$ 取值

2.交换枚举倍数与约数

3.用莫比乌斯函数求和替换

4.改写求和指标

5.得到一个整除分块的形式，处理一个函数的前缀和

最重要的还是保持恒等，利用 两种贡献 的思想。

一

有一个 积性函数 $f$，它与恒等函数 $1$ 的Dirichlet卷积 $g = f*1$ 如何计算？

假设 $n = \prod _ {i=1} ^{t} p _ {i} ^{ki}$ ，$g(n) = \sum _ {d|n} f(n)$ 。那么就有

$$\large g(n) = \prod _ {i=1} ^{t} \sum _ {j=0} ^{ki} f(p _ {i} ^{j}) \tag{11}$$

二

整数分块技巧。 求 $\sum _ {i=1} ^{n} f(i) \times \lfloor \frac n i \rfloor$

注意到 $\large \lfloor \frac n i \rfloor$ 只有 $O(\sqrt n)$ 种取值。对于固定的 $\lfloor \frac n i \rfloor$ ， $i$ 的取值为

$$\large \left[ \left \lfloor \frac n {\lfloor \frac n i \rfloor+1} \right \rfloor+1, \left \lfloor \frac n {\lfloor \frac n i \rfloor} \right \rfloor \right] \tag{12}$$

对于相同的 $\lfloor \frac n i \rfloor$ ，我们只需要计算 $f(i)$ 的前缀和 即可。复杂度即是 $O(\sqrt n)$。

同时有 $n,m$ 时同理。

三

假设 $a \ast b$ 已经是Dirichlet卷积，那么

$$\large id _ {k} \times (a \ast b) = (id _ {k} \times a) \ast (id _ {k} \times b) \tag{13}$$

再根据常用卷积 $id = \varphi \ast 1$ ，发现 $\varphi$ 是连接两个相邻 $id$ 的桥梁，即

$$\large (\varphi \times id _ {k}) \ast id _ {k} = id _ {k+1} \tag{14}$$

四

可以由两个常用卷积推出，

$$\large \varphi (n) = \sum _ {d|n} \mu (d) \times \frac n d \Longrightarrow \varphi = \mu \ast id \tag{15}$$

五

常见变换方式：约数与倍数的互换。

对于 $d,e,D=d \times e$ 三项贡献的这种，可以枚举 $D$ 将其化为狄利克雷卷积，也可以枚举 $d$和 $e$ 化成带下取整的式子；一般来讲前者往往易于预处理，可以应付多组询问，后者则在单次询问中有优秀表现。

六

最最最容易碰到的莫比乌斯套路。以后就直接作为结论 了：

现在有一个奇怪的函数 $f(n)$ ，不妨设 $n \leq m$ ，那么，

$$\large { \sum _ {i=1} ^ n \sum _ {j=1} ^ m f(\gcd(i,j)) \\ = \sum _ {d=1} ^ n f(d) \sum _ {i=1} ^ {\lfloor \frac n d \rfloor} \sum _ {j=1} ^ {\lfloor \frac m d \rfloor } [\gcd(i,j)=1] \\ = \sum _ {d=1} ^ n f(d) \sum _ {i=1} ^ {\lfloor \frac n d \rfloor} \sum _ {j=1} ^ {\lfloor \frac m d \rfloor } \sum _ {p|i,p|j} \mu(p) \\ = \sum _ {d=1} ^ n f(d) \sum _ {p=1} ^ {\lfloor \frac n d \rfloor} \mu(p) \cdot \lfloor \frac n {pd} \rfloor \cdot \lfloor \frac m {pd} \rfloor \\ = \sum _ {D=1} ^ n \sum _ {d|D} f(d) \cdot \mu(\frac D d) \cdot \lfloor \frac n D \rfloor \cdot \lfloor \frac m D \rfloor \tag{16}}$$

就变成要求 $f \ast \mu$ 的前缀和了，再套用分块即可。

杜教筛

问题的一般形式

给出一个奇怪的数论函数 $f(x)$ （simple一点像 $\mu, \varphi$ ）。接着给出了一个 $n$ ，一般有 $10^{10}$ 的范围。需要求 $S(n) = \sum _ {i=1} ^{n} f(i)$ 模一个大数的值。

构造

求出 $S(n)$ 会非常困难，考虑找出另一个函数 $g(x)$ ，考虑 $(f*g)(x)$ 的前缀和。

$$\large \sum _ {i=1} ^{n} \sum _ {j|i} f(i) g(\frac i j) = \sum _ {ij \leq n} f(i) g(j) = \sum _ {i=1} ^{n} g(i) S(\lfloor \frac n i \rfloor)$$

于是，

$$\large g(1)S(n) = \sum _ {i=1} ^{n} (f*g)(i) - \sum _ {i=2} ^{n} g(i) S(\lfloor \frac n i \rfloor)$$

要求&&时间复杂度&&Trick

需要保证 $(f*g)(x),g(x)$ 的前缀和都比较容易计算。

可以直接记忆化搜索，复杂度 $O(n^{\frac 3 4})$ 。

可以预处理前 $k$ 个前缀和，复杂度 $O(k + \frac n {\sqrt k})$ 。取 $k=n^{\frac 2 3}$ 最优，复杂度 $O(n ^ {\frac 2 3})$ 。

对于 $\mu(x),\varphi(x)$ 的前缀和，我们令 $g(x) = 1$ 即可。

特别重要的！

一个性质： $\large \left \lfloor \frac n {ab} \right \rfloor = \left \lfloor \frac {\left \lfloor \frac n a \right \rfloor} b \right \rfloor$

因为 $\frac n {n ^ {\frac 2 3}} \leq n ^ {\frac 1 3}$ ，根据上述性质，杜教筛在筛的过程中，会被计算的 $s(x)$ 只有 $O(n ^ {\frac 1 3})$ 个。

这个东西用于时间复杂度计算很有用！所以像分块套杜教筛啊，杜教筛套分块啊，复杂度都是对的！（只要都是不断整除 $n$）

还有一个 Trick ，我们不是要 HASH 吗，但是那个太慢了。

$S(x)$ 直接存到 $f[n/x]$ 里就好了（ $n$ 是全局的）

复杂的基本形式

%%%jiry_2

有时候， $f(x)$ 本身就是两个函数的积/Dirichlet卷积，通常令 $g(x) = 1$ ，可以进一步化简。

推柿子啦啦啦

来看一些有意思的题目。顺便.....

BZOJ3560 DZY Loves Math V 求 $\sum _ {i_1|a_1} \sum _ {i_2|a_2} ... \sum _ {i_n|a_n}$ 。

欧拉函数的性质。 考虑统计每一个质因子出现的次数，再相乘即可。注意 $p^0=1$ 要特殊考虑。

空间开不下？注意到一个 $ai$ 最多只会存在一个 $p > \sqrt {a_{max}}$ 。

51Nod1675 序列变换 给定序列 $a,b$ ，求存在多少对 $x,y$ 满足 $\gcd(x,y)=1,a_{b_x}=b_{a_x}$。

莫比乌斯反演的第二形式。 定义 $f(k)$ 为 $gcd(x,y)=k$ 的个数，定义 $F(k)$ 为 $k|\gcd(x,y)$ 的个数。显然 $F(k)$ 很容易求，于是用 $(10)$ 就好了。

BZOJ3561 DZY Loves Math VI 求 $\sum _ {i=1} ^ n \sum _ {j=1} ^ m lcm (i,j) ^ {\gcd(i, j)}$ 。

莫比乌斯反演，暴力。 虽然不是 $(16)$ 的形式，也可以用类似的套路，反演得到：

$$\sum _ {d = 1} ^ {n} d ^ d \cdot \sum _ {p = 1} ^ {\lfloor \frac n d \rfloor} \mu(p) \cdot p ^ {2d} \cdot \sum _ {i=1} ^ {\lfloor \frac m {pd} \rfloor} i ^ d \cdot \sum _ {j=1} ^ {\lfloor \frac n {pd} \rfloor } j ^ d$$

这个东西直接暴力嘛。。

BZOJ4816 [SDOI2017]数字表格 求 $\prod _ {i=1} ^ n \prod _ {j=1} ^ m fib(gcd(i,j))$ ，其中 $fib(n)$ 是斐波那契数。

莫比乌斯反演，前缀积。 同样也是 $(16)$ 的套路，只不过到了指数上面。同时前缀和变成了前缀积，同样也是 $O(n \log n)$ 暴力预处理。

BZOJ3529 [SDOI2014]数表 求 $\sum _ {i=1} ^ n \sum _ {j=1} ^ m \sigma _ 1(\gcd(i,j)) \cdot [\sigma_1(\gcd(i,j)) \leq a]$ 。多组询问。

莫比乌斯反演，离线。 哈哈哈，又是 $(16)$ 的套路。。于是就是要求：

$$\large \sum _ {d|D} \sigma_1 (d) \cdot \mu(\frac D d)$$

的前缀和。

然后这个 $a$ 的限制似乎有些难搞？注意到有多组数据，所以可以离线，按照 $a$ 排序。修改和求前缀和就交给树状数组了。

复杂度？ $O(n \log ^2 n + T \cdot \sqrt n \cdot \log n)$。

BZOJ4407 于神之怒加强版 求 $\sum _ {i=1} ^ n \sum _ {j=1} ^ m \gcd(i,j) ^ k$ 。

莫比乌斯反演，积性函数前缀和。 又是 $(16)$ 的套路（这句话说了多少遍了）。就是要求：

$$\sum _ {d|D} d ^ k \cdot \mu (\frac D d)$$

的前缀和。

然后这个是积性函数的狄利克雷卷积，可以线性筛。往往就需要利用 $\mu$ ，可以直接分情况。或者推公式，展开 $g(D)$ （这个方法比较万能）：

$$\large {g(n) \\ = \sum _ {d|n} d ^ k \mu(\frac n d) \\ = \prod _ {p_i} g(p_i ^{x_i}) \\ = \prod _{p_i} (p_i ^{kx_i} \cdot \mu(1) + p_i ^{k(x_i-1)} \cdot \mu(p_i)) \\ = \prod _ {p_i} p_i ^ {k(x_i-1)} \cdot (p_i ^k -1)}$$

BZOJ3994 [SDOI2015]约数个数和 求 $\sum _{i=1} ^n \sum _{j=1} ^m \sigma_0(i,j)$ 。

莫比乌斯反演，$\sigma_0$ 的性质。 这题需要利用 $\sigma_0$ 的性质：

$$\large \sigma_0 (n,m) = \sum _ {i|n} \sum _ {j|m} [\gcd(i,j)=1]$$

证明：考虑一个质因子 $p$ ，假设 $n$ 中有 $x$ 个，$m$ 中有 $y$ 个。那么根据约数个数定理，$\sigma_0(n,m) = \prod (x+y-1)$。而如果要使 $\gcd(i,j)=1$ ,每个质因子同样有 $x+y-1$ 种取法（$x$ 或 $y$ 为 $0$ ）。恰好是约数定理的形式。

接下来就是套路变换啦。

BZOJ3309 DZY Loves Math 对于正整数 $n$，定义 $f(n)$ 为 $n$ 所含质因子的最大幂指数。例如 $f(1960)=f(2^3 \times 5^1 \times 7^2)=3, f(10007)=1, f(1)=0$ 。给定正整数 $a,b$ ，求 $\sum _ {i=1} ^a \sum _ {j=1} ^m f( \gcd(i,j))$ 。

莫比乌斯反演，特殊性质函数的前缀和。 根据 $(16)$ ，我们只需要求 $g(D) = \sum _ {d|D} f(d) \mu ( \frac D d )$ 的前缀和即可。

但是，发现这个 $f(d)$ 不是积性函数，似乎就无法线性筛了。于是就要利用 $\mu(n)$ 的特殊性质。

将 $D$ 表示为质因数乘积的形式，如果 $\frac D d$ 对 $g(D)$ 有贡献，每个质因子的次数不会超过 $1$ 。 如果一个质因子 $p$ 在 $\frac D d$ 中，我们称选择 $p$ 。

引理：对于一个包含 $n\ (1 \leq n)$ 个元素的集合，选择奇数个元素的方案数的等于选择偶数个元素的方案数。

归纳法很容易证明。

我们知道，$\mu(D) = (-1) ^ k$ ，其中 $k$ 是选择的个数。

接下来分三种情况：（设所有质因子中，最大的次数为 $a$ ）

$D = p^a$ ， $g(p^a) = f(p^a) - f(p^{a-1}) = a - (a - 1) = 1$ 。

$D = p_1 ^{a_1} p_2 ^{a_2} ... p_m^{a_m}$ ，且 不 满足 $a_1 = a_2 = ... = a_m$，假设最大次数 $a$ 有 $b$ 个。考虑 $a-1$ 的贡献，此时最大次数的质因子都被选择，剩下的 $1 \leq m-b$ 个数可以任意选择，根据引理，正负全都被抵消了。考虑 $a$ 的贡献，由于 所有数中选择奇数与偶数个的方案，$a-1$ 时选择奇数与偶数个数的方案都相等 ，同样会正负都抵消。此时 $g(D) = 0$ 。

$D = p_1 ^{a_1} p_2 ^{a_2} ... p_m^{a_m}$ ，且有 $a_1 = a_2 = ... = a_m = a$。如果全部选择， $f(d) = a-1$ ，对 $g(D)$ 的贡献为 $(a-1) \times (-1)^m$ ;而其他情况下， $f(d)=a$，对 $g(D)$ 的贡献为 $a \times (-1) ^ {m-1}$ 。此时 $g(D) = -(-1)^m$ 。

为什么第三种情况套单独考虑？ 因为此时 $m-b=0$ ，不满足引理的条件，需要单独考虑。

同时也可以发现， 第一种情况没必要特殊考虑，同第三种情况。

最后，这个东西也是可以线性筛的。 利用 每个数只会被最小的质因子筛 用 $a[]$ 记录每一个数最小质因子的次数，$b[]$ 记录最小质因子的 $a[]$ 次，就可以递推了。

BZOJ3512 DZY Loves Math IV 求 $\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m \varphi (ij)$ ，$n \leq 10^5, m \leq 10^9$

欧拉函数的性质，莫比乌斯反演，杜教筛。 大爷的姿势。

令 $S(n,m) = \sum _ {i=1} ^ m \varphi (ni)$ 。

$$\large { S(n,m) \\ = \sum _ {i=1} ^ m \varphi (ni) \\ = \sum _ {i=1} ^ m \varphi ( \frac n {\gcd(i,n)}) \cdot \varphi(i) \cdot \gcd(i,n) \\ = \sum _ {i=1} ^ m \varphi(\frac n {\gcd(i,n)}) \cdot \varphi(i) \cdot \sum _ {d|i,d|n} \varphi(d) \\ = \sum _ {i=1} ^ m \varphi(i) \cdot \sum _ {d|i,d|n} \varphi(\frac n d) \\ = \sum _ {d|n} \varphi(\frac n d ) \cdot \sum _ {i=1} ^ {\lfloor \frac m d \rfloor } \varphi(di) \\ = \sum _ {d | n} \varphi(\frac n d) \cdot S(d, \lfloor \frac m d \rfloor )}$$

第二步，由于 $n,i$ 不一定互质，所以单独提出了 $\gcd$ ；第三步，巧妙地运用了 $(7)$ ；第四步，由于 $\frac n {\gcd(i,n)},d$ 互质，所以可以直接合并；第五步应该及其套路。

当 $n=1$ 时，需要大力杜教筛搞一搞。

嘛..

这个复杂度不会爆炸？

注意到，需要计算的 $S(n',m')$ ，一定满足 $m' = \lfloor \frac m {n'} \rfloor$（除了第一个），所以要计算的就很少啦。复杂度差不多是 $O((n ^ {\frac 2 3} + m ^ {\frac 3 2}) \times HASH)$ ？

还要HASH一下，同时，根据 $\varphi$ 的性质，可以先把 $n$ 中额外的质因子搞出来。

UPD 注意，第四步的推导是错误的，必须要满足 $|\mu(n)|=1$ ，这样才能保证互质（因为每个质因子都只有一个，只能存在于 $\frac n {\gcd(i,n)}$ 或者 $\gcd(i,n)$ ）。所以搞出额外的质因子是必须的。

51Nod1238 最小公倍数之和 $\sum _ {i=1} ^{n} \sum _ {j=1} ^{n} lcm(i,j)$

只是杜教筛。

两维的嘛..要先拆开来啦..

$$\large {f(n) \\ = \sum _ {i=1} ^{n} lcm(n,i)\\ = n \times \sum _ {i=1} ^{n} \frac i {\gcd (i, n)}\\ = n \times \sum _ {d|n} ^{n} \sum _ {id \leq n} i \times e(\gcd (i, \frac n d))\\ = n \times \sum _ {d|n} ^{n} \frac 1 2 \times (e(d) + d \times \varphi(d))\\ = \frac n 2 + \frac 1 2 \times n \times \sum _ {d|n} d \times \varphi(d)\\ }$$

最主要是搞出 $S(n) = \sum _ {i=1} ^n i \times \sum _ {d|i} d \times \varphi(d)$ 也就是 $id \times [(id \times \varphi) \ast 1] = (id _ 2 \times \varphi) \ast id$ 的前缀和。考虑如何消去难以计算的 $\varphi$ 。

我们需要卷上一个新的东西。考虑利用 $(7)$ 来消去。考虑卷上 $id _ 2$ 来提出括号中的 $id _ 2$ ，于是

$$\large id _ 2 \ast (id _ 2 \times \varphi) \ast id = id _ 2 \times (1 * \varphi) \ast id = id _ 3 \ast id$$

这个前缀和就比较好求辣。令 $h(i)$ 表示这个柿子的前缀和，于是（考虑展开后每个 $d$ 的贡献次数）

$$\large h(n) = \sum _ {d=1} ^{n} d \sum _ {id \leq n} i ^ 3$$

注意到不同 $i$ 的上限只有 $O(\sqrt n)$ 个，所以这个前缀和也可以分块！$g(x) = id _ 2$ 的前缀和也很容易计算。由于把 $S$ 划分为 $O(\sqrt n)$ 个子问题时也需要 $O(\sqrt n)$ 的时间复杂度，所以总的复杂度不变。仍然为 $O(n ^ {\frac 2 3})$ 。

发现很神奇的， $ANS = s(n)$ 。

另一种方法。 得到 $S(n) = \sum _ {i=1} ^n i \times \sum _ {d|i} d \times \varphi(d)$ 后，可以改变形式使得更容易筛。改为枚举 $i$ 是 $d$ 的多少倍。

$$\large {S(n) = \sum _ {i=1} ^n i \times \sum _ {d|i} d \times \varphi(d) \\ = \sum _ {i=1} ^ n i \times \sum _ {d=1} ^ {\lfloor \frac n d \rfloor} d ^ 2 \times \varphi (d)}$$

嗯，那么要求的就是 $id _ 2 \times \varphi$ 的前缀和，再分块。卷上 $id_ 2$ 。要求 $id_ 3$ 的前缀和。

题外话。 51Nod1227也是同样的方法，只是一开始得到的为 $(\varphi \times id) \ast 1$ 。51Nod1237大致方向差不多，只是推的过程简单很多。

如果用方法二，卷起来得到了 $id _ 2$ ，十分容易计算！

如果直接卷 $id$ 得到 $1 \ast id _ 2$ ，也可以应用方法一，里面套一层分块。

似乎两种方法本质一样，都需要进行一次约数/倍数变换。分块在外面或者里面。