题解：CF1278B A and B

Bc2_Ch1ckenPr1nce · 2026-10-22 08:24:51 · 题解

Solution

简单题。

钦定 A < B，则考虑先不断把 A 加 k，直到再加一次就大于 B 了为止。

此时的操作次数显然是满足 \cfrac{x(x + 1)}{2} > B - A 的最大的非负整数 x。

但现在 A 还是够不到，怎么办？再加一个 x + 1 即可，容易证明此时 A 一定大于 B。

我们便得到 A' = A + \cfrac{(x + 1)(x + 2)}{2}，令 d = A' - B。

怎么平掉这个差距？如果把前面的操作把 k 给 B 加，d 就会缩小 2k。

如果 d 是偶数，就可以在前面的操作中把 \cfrac{d}{2} 给 B 加，其余不变，此时操作次数没有额外添加，答案是 x + 1。

如果 d 是奇数且 x + 1 是偶数，在给 A 加一个 x + 2 就可以让 d 变成偶数了，然后在前面的操作中把 \cfrac{d + x + 2}{2} 给 B 加，其余不变，答案是 x + 2。

如果 d 是奇数且 x + 1 是奇数，在就可以在前面的操作中把 \cfrac{d - 1}{2} 给 B 加，其余不变。那怎么填补这个剩下的 1 的差呢？注意到给 A 加上 x + 2，给 B 加上 x + 3 等价于把 d 减少 1，答案是 x + 3。

Code

#include <bits/stdc++.h>

using namespace std;

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

const int kMaxN = 1e7 + 10;

ll a, b, x, ans;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> a >> b;
    if (a > b) {
      swap(a, b);
    }
    x = b - a, ans = sqrt(2 * x);
    for (; ans * (ans + 1) / 2 > x; -- ans);
    x = b - (a + ans * (ans + 1) / 2);
    if (!x) {
      cout << ans << '\n';
      continue;
    }
    x = b - (a + (ans + 1) * (ans + 2) / 2);
    if (x % 2) {
      if (ans % 2) {
        ans += 2;
      } else {
        ans += 3;
      }
    } else {
      ++ ans;
    }
    cout << ans << '\n';
  }
  return 0;
}