ARC150B题解

· · 题解

模拟赛场因为不会向上取整整除分块而死。

现在会了。

向上取整整除分块

他可以转化为向下取整。

发现：

\lceil\frac{b}{a}\rceil = \lfloor\frac{b}{a}\rfloor + [b \bmod a \neq 0] = \lfloor\frac{b}{a} + \frac{a-1}{a}\rfloor = \lfloor\frac{b + a - 1}{a}\rfloor

发现确定了 X 后，Y 随之确定。

于是答案为：

X + \lceil\frac{B}{X+A}\rceil(X+A)-B

向上取整整除分块即可，取左端点。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
int t;
int cil(int up, int dn) { return (up / dn) + (up % dn != 0); }
int gvx(int x) { return x + cil(b, a + x) * (a + x) - b; }
signed main() {
    cin >> t;
    while (t--) {
        cin >> a >> b;
        if (b <= a) {
            cout << a - b << '\n';
            continue;
        }

        int ans = min(b - a, gvx(0));
        for (int i = 1, r; i <= b; i = r + 1) {
            r = (b + i - 1) / ((b + i - 1) / i);
            if (i <= a)
                continue;
            else
                ans = min(ans, gvx(i - a));
        }
        cout << ans << '\n';
    }
    return 0;
}