记录编号	571102	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	4.302 s
提交时间	2022-05-07 12:27:40	内存使用	4.42 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 = 5e4+10;

int a, b, c, d, k;
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];
        }
    }
}

int calc(int n, int m) {
    int res = 0, l = 1, r;
    n /= k, m /= k;
    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(b);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    get_mu();
    rep (i, 2, N) mu[i] += mu[i - 1];
    while (t --) {
        std::cin >> a >> b >> c >> d >> k;
        std::cout << calc(b, d) - calc(b, c - 1) - calc(a - 1, d) + calc(a - 1, c - 1) << '\n';
    }
    return 0;
}