Chip Exchange

    1#include <bits/stdc++.h>
    2using namespace std;
    3#define int long long
    4using i128 = __int128_t;
    5void solve() {
    6    int a, b, ca, cb, k; cin >> a >> b >> ca >> cb >> k;
    7    auto good = [&] (int x) {
    8        if ((i128) a + ((i128) b + x) / cb * ca < (i128) k) return false;
    9        // how many use of change chip
    10        int begin = b / cb, end = (b + x) / cb;
    11        if (begin < end) {
    12            int last;
    13            if (ca >= cb) last = begin;
    14            else last = end - 1;
    15            // how many to give to achieve the worst distribution possible
    16            int worst = last * cb + cb - 1 - b;
    17            if (worst >= 0 && worst <= x) {
    18                if ((i128)a + x - worst + ((i128) b + worst) / cb * ca < (i128) k) return false;
    19            }
    20        }
    21        return true;
    22    };
    23    int lo = 0, hi = 1000000000000000000;
    24    // how much we give to b because minima always occur at give all to be or 1 before the multiple of cb
    25    while (lo < hi) {
    26        int mid = lo + (hi - lo) / 2;
    27        if (good(mid)) hi = mid;
    28        else lo = mid + 1;
    29    }
    30    cout << lo << '\n';
    31}
    32signed main() {
    33    ios::sync_with_stdio(0); cin.tie(0);
    34    int t; cin >> t;
    35    while (t--) {
    36        solve();
    37    }
    38    return 0;
    39}