P6055 GCD

题目大意

求

$$ \sum_{i=1}^N \sum_{j=1}^N \sum_{p=1}^{\left\lfloor \frac{N}{j}\right\rfloor} \sum_{q=1}^{\left\lfloor \frac{N}{j}\right\rfloor} [\gcd(i,j)=1][\gcd(p,q)=1] $$

分析

注意到一个神奇的事情

$$ \begin{aligned} &[\gcd(i,j)=1][\gcd(p,q)=1] \\ =&[\gcd(i,j) = 1][\gcd(pj,qj)=j]\\ =&[\gcd(i, pj, qj) = 1] \end{aligned} $$

因此

$$ \begin{aligned} ans &= \sum_{i=1}^N \sum_{p=1}^N\sum_{q=1}^N [\gcd(i, j, k) = 1] \\ &= \sum_{d=1}^N \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^3 \end{aligned} $$

整除分块即可。

int main() {
	ll n;
	cin >> n;
	Euler(1E6);
	SumMu smu(1E6);

	ll ans = 0;
	for (ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		int s = (smu.S(r) - smu.S(l - 1) + P) % P;
		ll t = n / l;
		ans += s * t % P * t % P * t % P;
	}
	cout << ans % P;

	return 0;
}

全部代码请看：Luogu/6x/P6055.cpp。