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

  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就一定同时是ij的约数,我们先枚举p,这样ij就只需要枚举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),你需要提前学过狄利克雷卷积才能看下去,如果没学过,就把它当一个常用结论记住吧!

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

    fg是两个函数

    (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)暴力求的