一 . 几个关于积性函数的常用结论。

  1. $\sum\limits_{d\mid n}\varphi(d)=n$

    证明步骤如下 :

    我们把$1-n$的数按与n的gcd分组,得到如下式子,由于每个数与n的gcd是固定的,每个数在$[\gcd(i, n)=1]$中只会被统计一次,所以下式等于n

    $n = \sum\limits_{d\mid n}\sum\limits_{i=1}^{n}[\gcd(i, n)= d]$

    $\Rightarrow \sum\limits_{d\mid n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i, \frac{n}{d})= 1]$

    $\Rightarrow \sum\limits_{d\mid n}\varphi(\frac{n}{d})$

    我们发现$\sum\limits_{d|n}\varphi(\frac{n}{d})\Leftrightarrow\sum\limits_{d|n}\varphi(d)$

    所以此结论得证。

  2. $\sum\limits_{d\mid n}\mu(d) = \varepsilon(n) = { 1, [n = 1] or\;0 ,[otherwise]}$

    证明步骤如下 :

    我们把n看成如$n = p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots p_s^{k_s} $的形式,并把枚举的d看成如$d = p_1^{q_1}p_2^{q_2}p_3^{q_3}\dots p_s^{q_s} $ 的形式

    我们发现当且仅当$q_1, q_2\dots q_s \le 1$的时候才对该和式有意义(参见莫比乌斯函数的取值),故我们枚举所有有意义的情况相当于求下面这个式子 :

    $C_s^0\times(-1)^0 + C_s^1\times (-1)^1 + C_s^1\times(-1)^2\dots C_s^s(-1)^s$

    典型的二项式展开形式

    如果你知道二项式定理,就会知道上式等价于$(1-1)^n$

    当n等于1的时候,我们单独讨论,显然答案是0。

    所以此结论得证。

  3. 反演结论 :$[gcd(i, j)=1] \Leftrightarrow\sum\limits_{p\mid \gcd(i, j)}\mu(p)$

    如果看懂了上一个结论,这个结论稍加思考便可以推出:如果$\gcd(i, j) = 1$的话,那么代表着我们按上个结论中枚举的那个n是1,也就是式子的值是1,反之,有一个与$[\gcd(i, j)=1]$相同的值 :0;

二. 小试牛刀,推两个式子 (我们总是默认n是小于等于m的,核心代码附在最后)

  1. $$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i, j)= d]$$

    我们把i看成$i’\times d$的形式,j看成$j’\times d$的形式,我们可以把d提取出来并除掉

    $\Rightarrow \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i, j)= 1]$

    运用之前的第三个结论,化成下式

    $\Rightarrow\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p\mid \gcd(i, j)}\mu(p)$

    我们既然$p$是$\gcd(i, j)$的约数,那么$p$就一定同时是$i$和$j$的约数,我们先枚举$p$,这样$i$和$j$就只需要枚举$p$的倍数了,总枚举量是一样的 :

    $\Rightarrow \sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}$

    考虑有多少个i和j会被记入答案,就是在$\frac{n}{d}、\frac{m}{d}$中有多少个p的倍数,答案是$\lfloor\frac{n}{dp}\rfloor $ 、$\lfloor\frac{m}{dp}\rfloor$

    所以,式子最终变成了这样 :

    $\Rightarrow \sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p) \lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor$

    之前接触过一点数论的话,由于是下取整,$\lfloor \frac{n}{dp}\rfloor$的取值最多只有$\sqrt{n}$个,所以我们可以在数轴上用$\lfloor\frac{n}{dp}\rfloor$、$\lfloor\frac{m}{dp}\rfloor$的不同取值,把他们分成最多$2\times \sqrt{n}$段并分段求和,另外再处理一下$\mu$函数的前缀和,总复杂度是$\Theta(\sqrt{N})$的。

  2. $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\gcd(i, j)$

    啊呀,没有给定的d了,没法除,这可如何是好?

    我们考虑造一个d即枚举d,也就是下式

    $\Rightarrow\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i, j)= d]$

    加快一点进度,后面的式子是我们刚刚看到过的,所以结合一下上一题的过程,我们来到了这个式子 :

    $\Rightarrow\sum\limits_{d=1}^{n}d\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor$

    但是这个式子还是不是很好算,我们需要进一步化简

    $dp$太丑了,我们设$Q = dp$并先枚举$Q$,这时的$p = \frac{Q}{d}$

    $\Rightarrow \sum\limits_{Q=1}^{n}\lfloor\frac{n}{Q}\rfloor\lfloor\frac{m}{Q}\rfloor\sum\limits_{d\mid Q}d\times \mu(\frac{Q}{d})$

    是不是有点没懂?

    我们之前的d是定义的Q的一个约数,我们枚举它就好啦

    我们把$\sum$遮住,他们太烦人了,如果不考虑枚举范围,其实就是$\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor\times d \times\mu(p)$嘛

    这时候已经枚举了Q和d,枚举Q的目的就是让dp消失,所以把dp直接替换成Q,d是枚举的,

    至于$\mu(p)$这不就是$\mu(\frac{Q}{d})$嘛~。

    如果你接触过反演,你会知道后面那一大串$\sum\limits_{d\mid Q}d\times\mu(\frac{Q}{d})$就是$\varphi(Q)$

    我们现在假装知道了它们就是$\varphi(Q)$,就只需要按刚刚的方法分段求前面分数的和,再维护一个$\varphi(Q)$的前缀和就好啦。

    我们来尝试证明一下它就是$\varphi(Q)$,你需要提前学过狄利克雷卷积才能看下去,如果没学过,就把它当一个常用结论记住吧!

    如果你没学过还想看下去,先来看一下狄利克雷卷积的一般形式,不会过多介绍,相信没学过的你一定看不懂

    设$f$和$g$是两个函数

    $ (f\ast g)(x)= \sum\limits_{d\mid n}f(d)g(\frac{n}{d})$

    另一个重要的性质是狄利克雷卷积具有结合律,且支持无限多个函数一起卷。

    两个积性函数的卷积一定是积性函数。

    如果你学过狄利克雷卷积,下面的过程我不会过多解释,但已经很详细的列出了推导过程,没看懂请仔细想想。

    设$f(x)=x,g(x)=\varphi(x),h(x)= 1$(这三个函数都是积性函数)

    $n = \sum\limits_{d\mid n}\varphi(d)$ 可以把它看成$g\ast h$的形式

    $\Rightarrow f(x) = (g\ast h)(x)$

    $\varepsilon(n) = \sum\limits_{d\mid n}\mu(d)$

    $\Rightarrow (\mu\ast h)(x) = \varepsilon(x)$

    在$\Rightarrow f(x) = (g\ast h)(x)$两侧一起卷上一个$\mu$函数

    $(f\ast\mu)=g\ast(h\ast\mu)$

    $(f\ast\mu)=g\ast\varepsilon$

    那么$f\ast\mu$是什么?带入狄利克雷卷积的定义式

    $f\ast\mu(Q) = \sum\limits_{d\mid Q}f(d)\mu(\frac{Q}{d})$

    为了更明显,我已经把n换成了Q,又因为定义$f(x)=x$我们发现这就是题中后面那一串。

    别急,后面还多个$\varepsilon$函数呢。

    我们把等式右边展开 :

    $\sum\limits_{d\mid n}\varphi(d)\varepsilon(\frac{n}{d})$

    我们想要让它等于$\varphi$函数

    考虑$\varepsilon$什么时候有意义 —— 当$\frac{n}{d}=1$的时候,即n = d的时候,因为其他取值都会导致$\varepsilon$为0

    那么这个卷积式其实就是$\varphi(n)\times 1 = \varphi(n)$啦

    到此,证毕,呼,真是累死~

    下面附上两个例题的核心代码

    int lst, ans = 0;for(int i = 1; i <= n; i = lst+1) {lst = min(n/(n/i), m/(m/i));ans += (sum[lst]-sum[i-1])*(n/i)*(m/i);// 对于第一题sum数组是莫比乌斯函数的前缀和,第二题则是欧拉函数的前缀和~}

    四道浅显易懂的推式子题 ,题解发在后面的博文中 :

    BZOJ 2820

    BZOJ 2301/1101/2045 三倍经验

    BZOJ 3529 离线+树状数组

    BZOJ 2693/2154 双倍经验

    看上去它们中的一些可能需要线性筛一个新函数,但是其实都是可以$\Theta(n\times \ln n)$暴力求的