题目大意

求

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

分析

显然欧拉反演

$$ \begin{aligned} ans &= \sum_{i=1}^n \sum_{j=1}^n ij \sum_{d \mid \gcd(i, j)} \varphi(d) \\ &= \sum_{d=1} d^2\varphi(d) \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} ij \\ &= \sum_{d=1} d^2\varphi(d) \frac{1}{4}\lfloor n/d\rfloor^2(\lfloor n/d \rfloor + 1)^2 \end{aligned} $$

整除分块 + 杜教筛即可。

int main() {
	int n, m;
	cin >> n >> m;
	int x = min(n, m);
	Euler(x + 1);

	vector<ll> sphi(x + 1);
	for (int i = 1; i <= x; i++) {
		sphi[i] = sphi[i - 1] + phi[i];
	}

	ll ans = 0;
	for (int l = 1, r; l <= x; l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		ans += 1ll * (sphi[r] - sphi[l - 1]) * (n / l) * (m / l);
	}
	cout << ans * 2 - 1ll * n * m;
	return 0;
}

全部代码请看：Luogu/3x/P3768.cpp。