「SDOI2015」约数个数和（莫比乌斯反演）

题目链接

题意：

 其中d(n)代表n的约数个数

思路：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 5;
int n, m, T, pr[N], mu[N], d[N], t[N], cnt;  // t 表示 i 的最小质因子出现的次数
bool bp[N];
void prime_work(int k) {
  bp[0] = bp[1] = 1, mu[1] = 1, d[1] = 1;
  for (int i = 2; i <= k; i++) {
    if (!bp[i]) pr[++cnt] = i, mu[i] = -1, d[i] = 2, t[i] = 1;
    for (int j = 1; j <= cnt && i * pr[j] <= k; j++) {
      bp[i * pr[j]] = 1;
      if (i % pr[j] == 0) {
        mu[i * pr[j]] = 0, d[i * pr[j]] = d[i] / (t[i] + 1) * (t[i] + 2),
               t[i * pr[j]] = t[i] + 1;
        break;
      } else
        mu[i * pr[j]] = -mu[i], d[i * pr[j]] = d[i] << 1, t[i * pr[j]] = 1;
    }
  }
  for (int i = 2; i <= k; i++) mu[i] += mu[i - 1], d[i] += d[i - 1];
}
int solve() {
  int res = 0, mxi = min(n, m);
  for (int i = 1, j; i <= mxi; i = j + 1)
    j = min(n / (n / i), m / (m / i)),
    res += d[n / i] * d[m / i] * (mu[j] - mu[i - 1]);
  return res;
}
signed main() {
  scanf("%lld", &T);
  prime_work(50000);
  while (T--) {
    scanf("%lld%lld", &n, &m);
    printf("%lld
", solve());
  }
  return 0;
}