rt，不知道为啥 WA 了。

再写就要和题解一样了（悲

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define RF(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
using LL = long long;
using Pii = pair<int, int>;
using Pll = pair<LL, LL>;

const int kN = 1e6 + 1;
const LL kM = 1e9 + 7;
const double kEps = 1e-9;

int t, n, m, mx, phi[kN];
double iv[kN];
bool v[kN];
vector<int> p;
LL ans, sphi[kN];

int D(int x, int y) { return x * iv[y] + kEps;}
int Nxt(int n, int x) {
  int v = D(n, x);
  if (!v) {
    return ::n;
  }
  return D(n, v);
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> t >> n >> m;
  mx = max(n, m);
  for (int i = 1; i <= mx; ++i) {
    iv[i] = 1.0 / i;
  }
  phi[1] = 1;
  for (int i = 2; i <= mx; ++i) {
    if (!v[i]) {
      p.push_back(i), phi[i] = i - 1;
    }
    for (int j : p) {
      int k = i * j;
      if (k > mx) {
        break;
      }
      v[k] = 1;
      if (i % j) {
        phi[k] = phi[i] * (j - 1);
      } else {
        phi[k] = phi[i] * j;
        break;
      }
    }
  }
  for (int i = 1; i <= mx; ++i) {
    sphi[i] = sphi[i - 1] + phi[i];
  }
  for (int i1, j1, i2, j2; t--; ) {
    cin >> i1 >> j1 >> i2 >> j2;
    --i1, --j1;
    if (i2 > j2) {
      swap(i2, j2), swap(i1, j1);
    }
    n = i2, m = min(n, (int)sqrt(j2 * 7));
    ans = 0;
    for (int i = 1; i <= m; ++i) {
      ans += phi[i] * (D(i2, i) - D(i1, i)) * (D(j2, i) - D(j1, i));
    }
    ans %= kM;
    for (int l = m + 1, r; l <= n; l = r + 1) {
      r = min({Nxt(i1, l), Nxt(i2, l), Nxt(j1, l), Nxt(j2, l)});
      ans += (sphi[r] - sphi[l - 1]) * (D(i2, l) - D(i1, l)) * (D(j2, l) - D(j1, l));
      ans %= kM;
    }
    cout << ans << '\n';
  }
  return 0;
}