题解：AT_arc150_b [ARC150B] Make Divisible

zhujiangyuan · 2024-10-10 08:13:00 · 题解

考虑枚举 X，则 B+Y 最小为 \left\lceil\dfrac{B}{A+X}\right\rceil\times (A+X)，则 Y 最小值为 \left\lceil\dfrac{B}{A+X}\right\rceil\times (A+X)-B。

所以确定 X 后，X+Y 的最小值为 X+\left\lceil\dfrac{B}{A+X}\right\rceil\times (A+X)-B。

发现若 \left\lceil\dfrac{B}{A+X}\right\rceil 相同，X 越小越好，考虑向上整除分块，x 每次取块的左端点即可。注意：整除分块枚举的是 A+X 的值。

时间复杂度 O(\sqrt{n})。

不会向上整除分块可以参考 oi-wiki。

int cil (int x, int y) { return (x + y - 1) / y; }
int get (int x) { return x + cil (b, a + x) * (a + x) - b;}
void solve () {
    int ans = 1e18;
    cin >> a >> b;
    if (a >= b) return cout << a - b << '\n', void ();
    ans = min (b - a, get (0));
    for (int l = 1, r; l < b; l = r + 1) {
        r = (b - 1) / ((b - 1) / l);
        if (l <= a) continue;
        else ans = min (ans, get (l - a));
    }
    ans = min (ans, get (b - a));
    cout << ans << '\n';
}