Səhər Səsi#12264

Səhər Səsi (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Problem aşağıdakı kimi tərcümə olunur:

$a \cdot x + b \cdot y = z$ a \cdot x + b \cdot y = z tənliyində $b$ -nin minimumunu tapın, burada $a, b$ qeyri-müsbət tam ədədlərdir.

$x, y, z$ x,y,z müsbət tam ədədlərdir və $a, b$ qeyri-müsbət tam ədədlərdir, $b$ $z$ -dən böyük ola bilməz, buna görə də $b$ -nin bütün mümkün dəyərlərini bruteforce edə bilərik və $\frac{z - b \cdot y}{x}$ \frac{z - b \cdot y}{x} dəyəri qeyri-müsbət tam ədəd olan minimum dəyəri tapırıq.

Komplekslik $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";
    }
}