Submission #72909391

---

Source Code Expand

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

long long T, n, m, a, b;

long long solve(long long n, long long a, long long b, long long m, long long c)
{
    if (n <= 0)
        return 0;
    if (a == 0)
    {
        if (c < 0)
            return n;
        else
            return 0;
    }
    long long k0 = (m - b + a - 1) / a;
    if (k0 > n - 1)
    {
        if (a == 1)
        {
            if (c < 0)
                return n;
            else
                return 0;
        }
        long long kmax = (-c - 1) / (a - 1);
        if (kmax < 0)
            return 0;
        long long r = min(n - 1, kmax);
        return r + 1;
    }
    long long cnt1 = 0;
    if (k0 > 0)
    {
        if (a == 1)
        {
            if (c < 0)
                cnt1 = min(k0, n);
            else
                cnt1 = 0;
        }
        else
        {
            long long kmax = (-c - 1) / (a - 1);
            if (kmax >= 0)
            {
                long long r = min(k0 - 1, min(n - 1, kmax));
                if (r >= 0)
                    cnt1 = r + 1;
            }
        }
    }
    long long n2 = n - k0;
    long long b2 = (a * k0 + b) - m;
    long long c2 = b2 + c - b - k0;
    return cnt1 + solve(n2, a, b2, m, c2);
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> a >> b;
        if (n == 0)
            cout << 0 << endl;
        if (a == 0)
            cout << min(n, b) << endl;
        if (a == 1)
        {
            if (b == 0)
                cout << 0 << endl;
            else
                cout << min(n, m - b) << endl;
        }
        cout << n - solve(n, a, b, m, b - 1) << endl;
    }
    return 0;
}

Submission Info

Judge Result