Cod sursa(job #2871490)

Utilizator AndreiV03Andrei Voicu AndreiV03 Data 14 martie 2022 20:55:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
	
 
#include <bits/stdc++.h>
#define FILES freopen("euclid3.in","r",stdin);\
              freopen("euclid3.out","w",stdout);
#define ll long long
#define fastio ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define MAX 100
#define pb push_back
#define mp make_pair
#define mod 666013
#define int ll
using namespace std;
int n,ans,ans2,a,b,c;
void solution(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return;
    }
    else
    {
        solution(b,a%b,x,y);
        int u = y ,u2 = x - (a / b) * y;
        x = u, y = u2;
    }
}
signed main()
{
    fastio
    FILES
    cin >> n;
    for(int i = 1;i <= n; ++i)
    {
        cin >> a >> b >> c;
        int r = __gcd(a,b);
        if(c % r)
        {
            cout << "0 0\n";
            continue;
        }
        solution(a,b,ans,ans2);
        cout << ans * (c / r) << ' ' << ans2 * (c / r) << '\n';
    }
}