Morning Voice#12264

Morning Voice (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

The problem translates to:

Find the minimum $b$ in the equation $a \cdot x + b \cdot y = z$ a \cdot x + b \cdot y = z where $a, b$ are non-negative integers.

Since $x, y, z$ x,y,z are positive integers and $a, b$ are non-negative integers, $b$ can't be bigger than $z$ , so we can bruteforce all possible values of $b$ and find the minimum one such that the value $\frac{z - b \cdot y}{x}$ \frac{z - b \cdot y}{x} is a non-negative integer.

Complexity $O (t \cdot z)$ \mathcal{O}(t \cdot z).


#include<bits/stdc++.h>
#define ll long long
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
using namespace std;

int main()
{
    d3
    ll T;
    cin >> T;
    while(T--)
    {
        ll x , y , z;
        cin >> x >> y >> z;
        ll ans = -1;
        for(ll i = 0 ; z>=i ; i++)
        {
            if(i*y>z)
                continue;
            ll e = z - i*y;
            if(e%x==0)
            {
                ans=i;
                break;
            }
        }
        cout << ans << "\n";
    }
}