题解：CF2043D Problem about GCD

· · 题解

Sol

我们充分发挥人类智慧，由于 A, B 一定是 G 的倍数，所以我们可以将不等式 l \le A \le B \le r 里的 l, r, A, B 除以一个 G：

\cfrac{l}{G} \le \cfrac{A}{G} \le \cfrac{B}{G} \le \cfrac{r}{G}

那么我们可以这么转化：

令

l' = \cfrac{l}{G},\ r' = \cfrac{r}{G},\ A' = \cfrac{A}{G},\ B' = \cfrac{B}{G}

但由于 l, r, A, B 均为整数，所以：

l' = \left\lceil\cfrac{l}{G}\right\rceil,\ r' = \left\lfloor\cfrac{r}{G}\right\rfloor

因为 \gcd(A, B) = g，所以：

\gcd\left(\cfrac{A}{G}, \cfrac{B}{G}\right) = 1

即

\gcd(A', B') = 1

我们可以考虑枚举 D = |A' - B'|，然后对每一个 1 \le L' \le R' - D，看是否有 \gcd(i,\ i + D) = 1。如果满足这个条件就可以直接输出 A' = G \cdot i，B' = G \cdot (i + D) 了，因为这已经做到 |A' - B'| 最优。这里注意一定要乘上 G。

虽然这看起来会超时，但由于某些原因，这可以通过本题。

具体证明可以参考 Atcoder arc137_a。

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 2e5 + 20;

ll l, r, g, a, b, d;

int main() { 
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> l >> r >> g, a = b = -1;
    l = (l + g - 1) / g, r = r / g;
    d = r - l;
    for (; d >= 0; -- d) {
      for (ll i = l; i <= r - d; ++ i) {
        if (__gcd(i, i + d) == 1) {
          a = i * g, b = (i + d) * g;
          break;
        }
      }
      if (a != -1 && b != -1) {
        break;
      }
    }
    cout << a << ' ' << b << '\n';
  }
  return 0;
}