分类: 狄利克雷卷积
计算两个数论函数的卷积的运算.
lp2257 YY的GCD
不妨设\(n<m\)
首先将原提问形式化,可以得到原式为:
$$\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{p\in P}[gcd(x,y)==p] $$
将所有的\(x,y\)都除以\(gcd(x,y)\),则原式可转化为:
$$\sum_{x=1}^{\lfloor \frac{n}{p} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{p} \rfloor}\sum_{p\in P}[gcd(x,y)==1]$$
然后,根据莫比乌斯函数的基本性质,我们有:
$$\sum_{d|n}