P1447 能量采集

题目大意

在 $n \times m$ 的花园中，设 $(0, 0) \to (i, j)$ 之间的格点数为 $k$，则 $(i, j)$ 的贡献为 $2k+1$。求整个花园的累计贡献。

分析

首先，格点数为 $\gcd(i, j) - 1$，不要拿 $\min(n/i, m/j)$ 去算，算不清楚的。

因此答案为

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

由欧拉反演

$$ \sum_{d \mid n} \varphi(d) = n $$

因此

$$ \begin{aligned} ans &= 2 \sum_{i=1}^n \sum_{j=1}^m \sum_{d \mid \gcd(i, j)} \varphi(d) - nm\\ &= 2\sum_{d=1}\varphi(d) \left\lfloor \frac{n}{d}\right\rfloor \left\lfloor \frac{m}{d}\right\rfloor - nm \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/1x/P1447.cpp。