Ранковий голос#12264

Ранковий голос (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	Hasan Saleh (MathModel)

Рішення

Проблема зводиться до:

Знайти мінімальне $b$ в рівнянні $a \cdot x + b \cdot y = z$ a \cdot x + b \cdot y = z, де $a, b$ - невід'ємні цілі числа.

Оскільки $x, y, z$ x,y,z - додатні цілі числа, а $a, b$ - невід'ємні цілі числа, $b$ не може бути більшим за $z$ , тому ми можемо перебрати всі можливі значення $b$ і знайти мінімальне таке, що значення $\frac{z - b \cdot y}{x}$ \frac{z - b \cdot y}{x} є невід'ємним цілим числом.

Складність $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";
    }
}