Some crazy white old man, calling himself the “Danger”, after watching a certain T.V series planned to research and invent his own “chemical”. After finishing his recipe, he found out he needs exactly n grams of the main ingredient to make it. If he makes with less than n grams, the mixture is not reactive enough and if he makes it with more than n grams, it simply explodes. He browsed Ebay and found only 2 sellers for the item. Seller A only sells n1 gram containers for c1 rupees each. Seller B only sells n2 gram containers for c2 rupees each. If it’s possible to buy exactly n grams from these 2 sellers, output the minimum cost of buying the ingredients

Link to the problem

I tried using linear diophantine equations, but the solution fails for large inputs.

My approach: 1. ax + by = c

1. find if solution exists based on gcd

2. if exists find any solution to x and y

3. if one of them is negative, try to convert them to positive values

4. if it cannot be converted, the solution doesn't exist

5. then try to reduce the cost using given conditions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(ll a, ll b, ll c, ll &x0, ll &y0, ll &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g)
        return false;
    x0 *= c / g;
    y0 *= c / g;
    ll lcm = a / g * b;
    x0 = x0 * a;
    y0 = y0 * b;
    if(x0 < 0) {
        ll delta = (abs(x0) / lcm + (abs(x0) % lcm != 0)) * lcm;
        x0 += delta;
        y0 -= delta;
    }
    else if(y0 < 0) {
        ll delta = (abs(y0) / lcm + (abs(y0) % lcm != 0)) * lcm;
        x0 -= delta;
        y0 += delta;
    }
    x0 /= a;
    y0 /= b;
    if(x0 < 0 || y0 < 0)
        return false;
    return true;
}


int main() {
    int t;
    cin>>t;
    while(t--) {
        ll n, n1, n2, a, b;
        cin>>n>>a>>n1>>b>>n2;
        ll x, y, g;
        if(!find_any_solution(n1, n2, n, x, y, g)) {
            cout<<"failed\n";
        }
        else {
            ll ax = n1 * x;
            ll bx = n2 * y;
            ll lcm = n1 / g * n2;
            if(n1 * b < n2 * a) {
                ll delta = (ax / lcm) * lcm;
                ax -= delta; bx += delta;
                cout<<(ax / n1)<<" "<<(bx / n2)<<"\n";
            }
            else {
                ll delta = (bx / lcm) * lcm;
                ax += delta; bx -= delta;
                cout<<(ax / n1)<<" "<<(bx / n2)<<"\n";
            }
        }
    }
    return 0;
}

Can someone help me solving this problem?