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

· · 题解

看了七八篇题解才懂公式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可以分拆成多个质因子的情况，上式依然成立。

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

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