WIKI

莫比乌斯

莫比乌斯函数

$$ \mu(n) = \left\{ \begin{array}{rl} 1 & \text{if } n=1,\\ (-1)^{r} & \text{if } n=p_1p_2\dots,\\ 0 & \text{if } 其他. \end{array} \right. $$

$\mu(n)$ 是个积性函数

定理1
$$ \sum\limits_{d|n}\mu(d) = \left\{ \begin{array}{rl} 1& \text{if } n=1,\\ 0 & \text{if } n>1\dots \end{array} \right. $$
设$f$ 为算术函数

$F$ 为 $f$的和 函数 满足 $F(n)=\sum\limits _{m|n}f(m)$

那么$f(n)=\sum\limits_{m|n}\mu(m)F(\frac nm)$

若$F$ 是积性函数,那么 $f$ 也是积性函数

[HAOI2011] Pronlem n

对于给出的 $n$ 个询问，每次求有多少个数对 $(x,j)$，满足 $a \le x \le n$，$c \le j \le m$，且 $\gcd(x,j) = k$，$\gcd(x,j)$ 函数为 $x$ 和 $j$ 的最大公约数。

对于 $100\%$ 的数据满足：$1 \le n,k \le 5 \times 10^4$，$1 \le a \le n \le 5 \times 10^4$，$1 \le c \le m \le 5 \times 10^4$。
$$ \begin{align} &\sum\limits^{n}_{i=1}\sum\limits_{j=1}^{m}[gcd(i,j)=k]\\ &\sum\limits^{\lfloor\large \frac n k \rfloor}_{i=1}\sum\limits_{j=1}^{\lfloor\large \frac m k \rfloor}[gcd(i,j)=1]\\ &\sum\limits^{\lfloor\large \frac n k \rfloor}_{i=1}\sum\limits_{j=1}^{\lfloor\large \frac m k \rfloor}\sum\limits_{m|gcd(i,j)}\mu(m)\\ &\sum\limits_{m=1}\mu(m)\sum\limits_{i=1}^{\lfloor\large \frac n k \rfloor}[m|i]\sum\limits_{j=1}^{\lfloor\large \frac m k \rfloor}[m|j]\\ &\sum\limits_{d=1}^{\large min(\lfloor \frac n k \rfloor,\lfloor \frac m k \rfloor)} \mu(d)\lfloor \frac n {kd} \rfloor\lfloor \frac m {kd} \rfloor \end{align} $$
code

// Luogu P2522 [HAOI2011] Problem b
// https://www.luogu.com.cn/problem/P2522 2024-03-13 16:43:46

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
constexpr int N = 5E4 + 10;
int n, m, a, b, c, d, k;
int tot;
int mu[N], primes[N];
bool st[N];
void init() {
  int tot = 0;
  mu[1] = 1;
  for (int i = 2; i < N; i++) {
    if (!st[i]) {
      primes[++tot] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= tot and i * primes[j] < N; j++) {
      st[primes[j] * i] = 1;
      if (i % primes[j] == 0) {
        mu[i * primes[j]] = 0;
        break;
      }
      mu[i * primes[j]] = -mu[i];
    }
  }
  for (int i = 1; i < N; ++i) mu[i] += mu[i - 1];
}
int sol(int a, int b) {
  int res = 0;
  for (int i = 1, j; i <= min(a, b); i = j + 1) {
    j = min(a / (a / i), b / (b / i));
    res += (mu[j] - mu[i - 1]) * (a / i) * (b / i);  // 代推出来的式子
  }
  return res;
}
void solve() {
  cin >> a >> b >> c >> d >> k;
  int ans = 0;
  ans += sol(b / k, d / k);
  ans -= sol((a - 1) / k, d / k);
  ans -= sol(b / k, (c - 1) / k);
  ans += sol((a - 1) / k, (c - 1) / k);
  cout << ans << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  init();
  int __;
  cin >> __;
  while (__--) solve();
  return 0;
}