Codeforces Round #846 (Div. 2)

E. Josuke and Complete Graph

题目抽象为求 \(\gcd(i,j)\) 有多少种 \((i\neq j,i\in [l,r],j\in [l,r])\)，如：当 \(l=2,r=4\) 时，\(\gcd(2,4)=2\)，\(\gcd(2,3)=\gcd(3,4)=1\)，答案为 \(2\)。

考虑分块。

要判断是否存在 \(\gcd(i,j)=x\)，那么就要判断 \([l,r]\) 能否选出 \(2\) 个 \(x\) 的倍数。即 \(\frac{r}{x}-\frac{l-1}{x}\geq 2\)。

\(r-l+1\geq 2\) 就一定存在 \(\gcd(i,j)=1\) 的，\(r-l+1\geq 4\) 就一定存在 \(\gcd(i,j)=2\) 的，\(r-l+1\geq 6\) 就一定存在 \(\gcd(i,j)=3\) 的。

\(\frac{r}{x}\) 的值可以用整除分块算出，\(\frac{l-1}{x}\) 的值也可以用整除分块算出。将算出的这些值用双指针进行组合，即可得到所有可能的取值。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
  i64 l, r;
  cin >> l >> r;
  i64 ans = (r - l + 1) / 2;
  i64 x = (r - l + 1) / 2 + 1;
  while ((r - l + 1) / x >= 1) {
    i64 rk = r / x, lk = (l - 1) / x;
    if (rk - lk >= 2) {
      i64 R = r / rk;
      ans += R - x + 1;
      x = R + 1;
    } else if (lk) {
      i64 L = (l - 1) / lk;
      x = L + 1;
    } else {
      break;
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}