记录编号	612776	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BZOJ 1101]Zap	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	4.748 s
提交时间	2026-02-26 11:39:28	内存使用	4.14 MiB

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
int mu[MAXN], pr[MAXN];
bool vis[MAXN];
int sum[MAXN], tot = 0;

void init(int n){
	mu[1] = 1;
	for(int i = 2;i <= n;i ++){
		if(!vis[i]){
			pr[++ tot] = i;
			mu[i] = -1;
		}
		for(int j = 1;j <= tot && pr[j] * i <= n;j ++){
			vis[pr[j] * i] = 1;
			if(i % pr[j] == 0){
				mu[pr[j] * i] = 0;
				break;
			}
			mu[pr[j] * i] = -mu[i];
		}
	}
	for(int i = 1;i <= n;i ++){
		sum[i] = sum[i - 1] + mu[i];
	}
}

int solve(){
	int a, b, d, ans = 0;
	cin >> a >> b >> d;
	if(a > b) swap(a, b);
	a /= d, b /= d;
	for(int l = 1, r;l <= a;l = r + 1){
		r = min(a / (a / l), b / (b / l));
		ans += (sum[r] - sum[l - 1]) * (a / l) * (b / l);
	}
	return ans;
}

int main(){
	init(50000);
	int t; cin >> t;
	while(t --){
		cout << solve() << '\n';
	}
	return 0;
}