P2257 YY 的 GCD

题目大意

即求

$$ \sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) \in \mathbb{P}] $$

分析

先转化一下

$$ \sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) \in \mathbb{P}] = \sum_{p}\sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) = p] $$

在 P2522 中得到

$$ \sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j) = k] = \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tk} \right\rfloor \left\lfloor \frac{y}{tk} \right\rfloor $$

代入有

$$ \sum_{p} \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tp} \right\rfloor \left\lfloor \frac{y}{tp} \right\rfloor $$

令 $T = tp$，$T$ 的上界应还是 $\min(x,y)$，代入有

$$ \sum_{T=1}^{\min(x,y)} \left\lfloor \frac{x}{T} \right\rfloor \left\lfloor \frac{y}{T} \right\rfloor \sum_{p \mid T} \mu\left(\frac{T}{p}\right) $$

后面那个在 Euler 筛后再求和一下，是可以预处理的。

const ll MN = 1e7 + 100;

int mu[MN], f[MN], dp[MN];

bool notp[MN];
int prime[MN/10], cnt;
void sieve(int n) {
	mu[1] = 1;
	for (ll i = 2; i <= n; i++) {
		if (!notp[i])
			prime[++cnt] = i, mu[i] = -1;
		int t = n / i;
		for (ll j = 1; j <= cnt; j++) {
			if (prime[j] > t)
				break;
			notp[i * prime[j]] = true;
			if (i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = - mu[i];
		}
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= cnt; j++) {
			ll t = i * prime[j];
			if(t > n)
				break;
			dp[t] += mu[i];
		}
	}
	for (ll i = 1; i <= n; i++)
		f[i] = f[i - 1] + dp[i];
}

此时 $dp(T)$ 中存的是 $\displaystyle\sum_{p \mid T} \mu\left(\frac{T}{p}\right)$，$f_i$ 是其前缀和。

之后整数分块即可

ll calc(ll a, ll b) {
	ll mab = min(a, b);
	ll sum = 0;
	for (ll l = 1, r; l <= mab; l = r + 1) {
		r = min(a / (a / l), b / (b / l));
		sum += (f[r] - f[l - 1]) * (a / l) * (b / l);
	}
	return sum;
}

int main() {
	ll ttt = rr();
	sieve(MN - 10);
	for (ll i = 1; i <= ttt; i++) {
		ll a = rr(), b = rr();
		printf("%lld\n", calc(a,b));
	}
	return 0;
}

相似题目

P2568 GCD

即 $M = N = n$ 的特殊情况，可以再优化。即求

$$ \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j) \in \mathbb{P}] $$

化简有

$$ \begin{aligned} \sum_{p} \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j) = p] &= \sum_{p} \sum_{i=1}^{\lfloor n/p\rfloor} \sum_{j=1}^{\lfloor n/p\rfloor} [\gcd(i,j) = 1]\\\\ &= \sum_{p} \left(2\sum_{j=1}^{\lfloor n/p\rfloor} \sum_{j=1}^{i} [\gcd(i,j) = p] - 1\right)\\\\ &= \sum_{p}\left( 2\sum_{i=1}^{\lfloor n/p \rfloor} \varphi(i) - 1 \right) \end{aligned} $$

预处理出 $\varphi(i)$ 的前缀和后，对每个素数筛一遍即可。