Luogu P3455 [POI2007]ZAP-Queries

gate

(large sumlimits_{i=1}^{a}sumlimits_{j=1}^{b}[gcd(i,j)=x])
(=large sumlimits_{i=1}^{frac{a}{x}}sumlimits_{j=1}^{frac{b}{x}}[gcd(i,j)=1])
(=large sumlimits_{i=1}^{frac{a}{x}}sumlimits_{j=1}^{frac{b}{x}} sumlimits_{d|i,d|j}mu(d))
(=large sumlimits_{d}mu(d)sumlimits_{i=1}^{frac{a}{xd}}sumlimits_{j=1}^{frac{b}{xd}})
(=large sumlimits_{d}mu(d)lfloorfrac{a}{xd} floorlfloorfrac{b}{xd} floor)

预处理出(mu(i))的前缀和，
求(large lfloorfrac{a}{xd} floorlfloorfrac{b}{xd} floor)可以整除分块，最多有(2sqrt{a} + 2sqrt{b})种取值。
注意((a/i)*(b/i))不要忘记打括号！因为是整除...

code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

const int maxn = 5e4+10;
const int N = 5e4;

int n,prime[maxn],mu[maxn],cnt;
long long a,b,d,f[maxn];
bool vis[maxn];

void Prime() {
	f[1] = mu[1] = 1;
	for(int i = 2; i <= N; i++) {
		if(!vis[i]) {
			prime[++cnt] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= cnt && i*prime[j] <= N; j++) {
			vis[i*prime[j]] = true;
			if(i % prime[j])
				mu[i*prime[j]] = -mu[i];
			else {
				mu[i*prime[j]] = 0;
				break;
			}
		}
		f[i] = f[i-1]+mu[i];
	}
}

long long solve(long long a,long long b) {
	long long ans = 0;
	if(a > b) swap(a,b);
	for(long long i = 1,r; i <= a; i = r+1) {
		r = min(a/(a/i),b/(b/i));
		ans += (f[r]-f[i-1]) * (a/i) * (b/i);
	}
	return ans;
}

int main() {
	Prime();
	scanf("%d",&n);
	while(n--) {
		scanf("%lld%lld%lld",&a,&b,&d);
		printf("%lld
",solve(a/d,b/d));
	}
	return 0;
}