约数个数函数的一个性质证明，以及其推广

[洛谷P3327 [SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327) [洛谷P4619 [SDOI2018]旧试题](https://www.luogu.com.cn/problem/P4619) 要用到这个性质，而且网上几乎没有能看的证明，所以特别提出来整理一下。 ## Original ### 二维 >$$ >d(AB) = \sum_{x|A} \sum_{y|B} [\gcd (x,y) = 1] >$$ > >其中 $d$ 是约数个数函数，即 $d_k (n) = \sum_{d|n} 1$ （看上去比较不可思议对吧） 右侧的枚举，一部分因子算多了（比如当 $\gcd(x,y)=1$ 且额外有 $x|B,y|A$ 时，可以枚举出 $x*y = y*x$ ），一部分因子又没有算（比如当 $\gcd(A,B) \not= 1$ 时的 $A*B$ ）。但是算多和算少之间达成了诡异的平衡。 首先考虑 $A,B$ 互质的情况。显然此时右式中的 $[\gcd (x,y) = 1]$ 恒成立。而左式可以通过积性函数的性质拆开。两侧都为 $d(A)*d(B)$ ，成立。（其实并没有按是否互质讨论的必要，但是这样想能让我们的思路更加清晰） 那么考虑 $\gcd(A,B) \not= 1$ 时的情况。不妨先证明 $A = p^a, B = p^b$ （ $p$ 是素数，这两个 $p$ 是同一个数）时等式成立。 这部分的证明是容易的。根据约数个数的定义，左式显然为 $a+b+1$。对于右式，设 $x = p^c, y= p^d$ ，若要使 $[\gcd (x,y) = 1]$ 成立， $c,d$ 中至少有一个为 $0$ 。那么当 $b=0$时，$c \in [0, a]$；当 $a=0$ 时， $c \in [0,b]$ ；其他情况都不满足条件。排除重复的 $c=0, d=0$ ，共有 $a+b+1$ 个情况成立，与左式相同，故等式成立。 讨论更加一般的情况。有了前面的证明，我们考虑将 $AB$ 分解质因数后食用，分解后的每一项的形式为 $p^{a+b}$ 。左边根据约数个数基本性质“指数加一连乘积”，即每一个 $p$ 对应的 $(a+b+1)$ 之积。对于右侧，前证说明对于每个 $p$ ，合法的 $c,d$ 的选择有对应的 $a+b+1$ 种，要让 $[\gcd(x,y)=1]$ 需要每一个 $p$ 都是合法情况。而每个 $p$ 相对独立，其本质就是许多个“选择”，直接用乘法原理合并起来即可，于是也与左式相同。 用通俗一点的说法，我不管其他的 $p$ 到底需要让 $x,y$ 满足什么样的条件才能使 $[\gcd(x,y)=1]$ ，反正在我这个 $p$ 这里只有 $a+b+1$ 种方案合法。 总之这样就证毕了。 证明思路很像积性函数的合并，也许对其他一些积性函数命题的证明这种方法也管用。 ### 高维 对于形如 $$ d(ABC) = \sum_{x|A} \sum_{y|B} \sum_{z|C} [\gcd (x,y) = 1] [\gcd (y,z) = 1] [\gcd (x,z) =1] $$ 的高维拓展，证明思路基本相同，不再赘述。（如果觉得有点迷可以先跳过，Extended里的证明更加接近本质） --- ## Extended (update 2020/03/08) 下面研究 Original 推广到广义约数个数函数的形式。 ### 二维 >$$ >\sigma_k (AB) = \sum_{x|A} \sum_{y|B} [\gcd(x,y)=1] (x \frac{B}{y})^k = \sum_{x|A} \sum_{y|B} [\gcd(x,\frac{B}{y})=1] (x y)^k >$$ > >其中 $\sigma_k$ 是广义的约数个数函数，即 $\sigma_k (n) = \sum_{d|n} d^k$ 显然中式和右式是等价的。现证明左式和右式等价。 证明思路与上面基本一致。同样的，我们先解决 $A=p^a, B=p^b$ 的情况。 首先，直接由定义得出左式： $$ 左式 = \sum_{i=0}^{a+b} p^{ik} $$ 同样设 $x=p^c, y=p^d$ 。分析 $[\gcd(x,\frac{B}{y})=1]$ 的意义，它的意思是若 $x$ 中不含 $p$ （ $c=0$ ），则 $y$ 可以随便选（ $d \in [0,b]$ ）；若 $x$ 中含 $p$ （ $c \in [1,a]$ ），则 $y$ 就必须包含所有的 $p$ （ $d=b$ ），否则 $\frac{B}{y}$ 里就含有 $p$ 了；其他情况不满足条件 。 即合法的情况为 $(0,[0,b])$ 和 $([1,a],b)$ 。 那么，根据右式的形式，可以得出 $$ \begin{aligned} 右式 &= \sum_{i=0}^b p^0 p^i + \sum_{i=0}^a p^i p^b \\ &= \sum_{i=0}^b p^i + \sum_{i=0}^a p^{b+i} \end{aligned} $$ 该式实际上只是将左式的枚举从 $b$ 那里切开了。两式是等价的。 那么和上面一样的，对于一般的情况分解质因数，对每一个 $p$ 分别考虑，积性合并即可。全部乘起来的依据也是乘法原理（ $\sum * \sum$ 就是在枚举所有的方案对应贡献乘积之和）。可能有人问：这里的 $B$ 不是发生变化了吗？其实 $B$ 充当的是一个 $y$ 的全集，不是 $p^b$ 了也不影响 $x,y$ 的取值，所以是没有关系的。可以参考一下 Original 里“通俗一点的说法”。 ### 高维 形如 $$ \sigma_k (ABC) = \sum_{x|A} \sum_{y|B} \sum_{z|C} [\gcd(x,\frac{B}{y})=1] [\gcd(y,\frac{C}{z})=1] [\gcd(x, \frac{C}{z}=1)] (x y z)^k $$ 的高维拓展， $\gcd$ 部分就是如 $x-y$ ， $x-z$ ， $y-z$ 两两配对的形式，这样来限制取值范围。 证明思路基本相同，同样写出合法情况 $(0,0,[0,c])$ ， $(0,[1,b],c)$ ， $([1,a],b,c)$ ，对应 $p^{a+b+c+1}$ ，就容易证明了。 已打表检验正确。