Cod sursa(job #2079510)

Utilizator MaligMamaliga cu smantana Malig Data 1 decembrie 2017 14:41:57
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#include <stack>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 5e2 + 5;
const ll inf = 1e18 + 5;

ll T;

ll euclid(ll x,ll y,ll& a,ll& b) {
    if (y == 0) {
        a = 1;
        b = 1;
        return x;
    }

    ll a0,b0,d;
    d = euclid(y,x%y,a0,b0);

    a = b0;
    b = a0 - b0 * (x/y);
    return d;
}

int main() {
    in>>T;

    while (T--) {
        ll x,y,a,b,c;
        in>>x>>y>>c;

        ll d = euclid(x,y,a,b);
        if (c % d == 0) {
            a *= c/d;
            b *= c/d;

            out<<a<<' '<<b<<'\n';
        }
        else {
            out<<"0 0\n";
        }
    }

    return 0;
}