BZOJ4659：lcm

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

传送门

题目所给的不合法的条件可以转化为

\[\exists p,p^2|gcd(a,b) \Leftrightarrow \mu(gcd(a,b))\ne 0
\]

那么

\[ans=\sum_{a=1}^{A}\sum_{b=1}^{B}[\mu(gcd(i,j))\ne 0]\frac{ab}{gcd(a,b)}
\]

不妨假设 \(A\le B\)，枚举 \(gcd\) 之后经典莫比乌斯反演

设 \(S(x)=\sum_{i=1}^{x}i\)

得到

\[\sum_{i=1}^{A}S(\lfloor\frac{A}{i}\rfloor)S(\lfloor\frac{B}{i}\rfloor)\sum_{d|i}[\mu(d)\ne 0](\frac{i}{d})^2\mu(\frac{i}{d})d
\]

后面的狄利克雷卷积是一个积性函数，直接线性筛

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned int uint;

const int maxn(4e6 + 5);

const int mod(1 << 30);

int test, pr[maxn], tot, n, m, cnt[maxn], pwd[maxn];

uint ans, s[maxn];

bitset <maxn> ispr;

inline uint S(uint x) {

	return (x & 1) ? (x + 1) / 2 * x : x / 2 * (x + 1);

}

int main() {

	register uint i, j;

	ispr[1] = 1, s[1] = 1;

	for (i = 2; i < maxn; ++i) {

		if (!ispr[i]) pwd[i] = pr[++tot] = i, s[i] = i - i * i, cnt[i] = 1;

		for (j = 1; j <= tot && i * pr[j] < maxn; ++j) {

			ispr[i * pr[j]] = 1;

			if (i % pr[j]) {

				s[i * pr[j]] = s[i] * s[pr[j]];

				pwd[i * pr[j]] = pr[j], cnt[i * pr[j]] = 1;

			}

			else {

				cnt[i * pr[j]] = cnt[i] + 1, pwd[i * pr[j]] = pwd[i] * pr[j];

				if (cnt[i] == 1) s[i * pr[j]] = -(uint)pr[j] * pr[j] * pr[j] * s[i / pwd[i]];

				else s[i * pr[j]] = 0;

				break;

			}

		}

	}

	for (i = 2; i < maxn; ++i) s[i] += s[i - 1];

	scanf("%d", &test);

	while (test) {

		scanf("%d%d", &n, &m), test--;

		if (n > m) swap(n, m);

		for (ans = 0, i = 1; i <= n; i = j + 1) {

			j = min(n / (n / i), m / (m / i));

			ans += (s[j] - s[i - 1]) * S(n / i) * S(m / i);

		}

		printf("%u\n", ans % mod);

	}

    return 0;

}