P1829 能量采集

题目大意

计算

$$ \sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i, j) $$

分析

先化 $\gcd$ 出来

$$ ans = \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{\gcd(i, j)} $$

显然套 Mobius 反演，朝着那个方向化就行。

$$ \begin{aligned} ans &= \sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^m \frac{ij}{d} [\gcd(i, j) = d] \\ &= \sum_{d=1} d \sum_{i=1}^{n / d} \sum_{j=1}^{m / d} ij [\gcd(i, j) = 1] \\ &= \sum_{d=1} d \sum_{x=1}^{\min(n/d, m/d)} x^2\mu(x) S_1 \left(\left\lfloor \frac{m}{dx} \right\rfloor \right) S_1 \left(\left\lfloor \frac{n}{dx} \right\rfloor \right) \end{aligned} $$

其中 $x^2 \mu(x)$ 可以线性筛预处理，后者可以整除分块嵌套一下。

Z iv2 = Z(2).inv();

Z S1(Z x) {
	return x * (x + 1) * iv2;
}

Z sol1(int md, int nd) {
	Z ans = 0;
	for (int l = 1, r; l <= min(md, nd); l = r + 1) {
		r = min(md / (md / l), nd / (nd / l));
		ans += (smu[r] - smu[l - 1]) * S1(nd / l) * S1(md / l);
	}
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	Z ans = 0;
	Euler(max(n, m) + 10);
	for (int l = 1, r; l <= min(n, m); l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		ans += (S1(r) - S1(l - 1)) * sol1(n / l, m / l);
	}
	cout << ans;
	return 0;
}

全部代码请看：Luogu/1x/P1829.cpp。