记录编号	571095	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3609.[BZOJ 1101]Zap	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	6.415 s
提交时间	2022-05-07 11:22:05	内存使用	4.05 MiB

#include <bits/stdc++.h>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define rep(_x, _y, _z) for (int _x = (_y); _x <= _z; ++ _x)

using i64 = long long;
const int N = 1e5+10;

int t, a, b, d;
int primes[N], mu[N], cnt;
bool st[N];

void get_mu() {
    mu[1] = st[1] = 1;
    rep (i, 2, N) {
        if (!st[i]) primes[++ cnt] = i, mu[i] = -1;
        rep (j, 1, cnt && primes[j] < N / i) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                mu[i * primes[j]] = 0;
                break;
            }
            mu[i * primes[j]] = - mu[i];
        }
    }
}

i64 calc(int n, int m) {
    i64 res = 0, l = 1, r;
    while (l <= std::min(n, m)) {
        r = std::min(n / (n / l), m / (m / l));
        res += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
        l = r + 1;
    }
    return res;
}

int main() {
    OPEN(zap);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> t;
    get_mu();
    rep (i, 2, N) mu[i] += mu[i - 1];
    while (t --) {
        std::cin >> a >> b >> d;
        std::cout << calc(a / d, b / d) << '\n';
    }
    return 0;
}