题目大意

即求

$$ \sum_{i=a}^b \sum_{j=c}^d [\gcd(i,j) = k] $$

分析

容易想到，独立出函数 $f(k)$ 使得

$$ f(k) = \sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j) = k] $$

利用 Mobius 反演化简，设 $F(d)$

$$ F(n) = \sum_{n \mid d} f(d) = \sum_{i=1}^x \sum_{j=1}^y [n \mid i][n \mid j] = \left\lfloor \frac{x}{n} \right\rfloor \left\lfloor \frac{y}{n} \right\rfloor $$

反演化简有

$$ f(n) = \sum_{n \mid d} \mu\left(\frac{d}{n}\right)F(d) = \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tn} \right\rfloor \left\lfloor \frac{y}{tn} \right\rfloor $$

预处理出 $\mu(t)$ 的前缀和，剩下的就是一个二重分块了。

const ll MN = 50000;

bool notp[1000001];
int prime[200001], cnt, mu[MN];

void Mobius(int n); // 预处理 Mobius 函数

ll f(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 += (mu[r] - mu[l - 1]) * (a / l) * (b / l);
	}
	return sum;
}

int main() {
	ll ttt = rr();
	Mobius(MN - 1);
	for (ll i = 1; i <= MN - 1; i++)
		mu[i] += mu[i - 1];
	for (ll i = 1; i <= ttt; i++) {
		ll a = rr(), b = rr(), c = rr(), d = rr();
		ll k = rr();
		a--, c--;
		a /= k, b /= k, c /= k, d /= k;
		ll ans = f(b, d) - f(a, d) - f(b, c) + f(a, c);
		printf("%lld\n", ans);
	}
	return 0;
}

类似题目

P2158 仪仗队：即 $k = 1$ 的特殊情况。

P3455 ZAP-Queries：几乎一样。

P2257 YY 的 GCD：比这题难，单独开篇。