悬2关

求调P2522

#include <bits/stdc++.h>
#define int long long
using namespace std;
int mu[1000005];
int flg[1000005];
int p[1000005];
int sum[1000005];
int tot;
void getMu(int n) {
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!flg[i]) p[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i];
}
signed main() {
	getMu(50000);
	int t; cin >> t;
	for (int i = 1; i <= t; i++) {
		int a, b, c, d, k; cin >> a >> b >> c >> d >> k;
		--a; --c;
		a /= k; b /= k; c /= k; d /= k;
		int ans = 0;
		for (int l = 1, r; l <= min(b, d); l = r + 1) {
			r = min(b / (b / l), d / (d / l));
			ans += (sum[r] - sum[l - 1]) * (b / l - a / l) * (d / l - c / l);
		}
		cout << ans << endl;	
	}
	return 0;
}