题解 P3327 【[SDOI2015]约数个数和】

2018-05-16 22:25:13


看了七八篇题解才懂公式$$d(xy)=\sum_{i|x} \sum_{j|y} [gcd(x,y)==1]$$的证明,在这里写一下我的个人看法—— 我们不妨将每一个质因子分开考虑,设x,y分别含有a,b个质因子p (这说明$p^a|x, p^{a+1}$不整除x, b和y同理), 显然乘积xy会含有a+b个p质因子,在等式左边,我们选质因子p的不同选法有a+b+1种,就是选0次,1次,..., a+b次; 在等式右边,选质因子p的不同选法也有a+b+1种,即从x中选(1~a)个y中选0个、从x中选0个y中选(1~b)个、x和y中各选0个,共a+b+1种。

因此,对于x=p^a和y=p^b, 上式成立。

又因为质因子之间互相独立,所以对于x和y可以分拆成多个质因子的情况,上式依然成立。

后面的莫比乌斯反演部分参照楼下。

本人菜鸟,上述论证有不当之处敬请指教,谢谢。