P3327约数个数和怎么为？
摘要：P3327 [SDOI2015] 约数个数和 大意 给定 (n, m)，求 (sum_{i=1}^n sum_{j=1}^m d(ij))，其中 (d(x)) 表示 (x) 的约数个数。 思路 [d(ij) = su
P3327 [SDOI2015] 约数个数和
大意
给定 \(n, m\)，求 \(\sum_{i=1}^n \sum_{j=1}^m d(ij)\)，其中 \(d(x)\) 表示 \(x\) 的约数个数。
思路
\[d(ij) = \sum_{x|i} \sum_{y|j} [\gcd(x, y) = 1]
\]
将该恒等式代入原式：
\[\text{Ans} = \sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} [\gcd(x, y) = 1]
\]
通过更换求和次序，先枚举 \(x\) 和 \(y\)。