Cod sursa(job #2019909)

Utilizator MaligMamaliga cu smantana Malig Data 8 septembrie 2017 20:13:25
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>

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

#define ll long long
#define ull unsigned long long
#define pb push_back
const int NMax = 1e3 + 5;

ll euclid(ll,ll,ll&,ll&);

int main() {
    ll T;
    in>>T;

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

        bool minusA = false,minusB = false;
        if (a < 0) {
            minusA = true;
            a = -a;
        }
        if (b < 0) {
            minusB = true;
            b = -b;
        }

        d = euclid(a,b,x,y);
        if (minusA) {
            x = -x;
        }
        if (minusB) {
            y = -y;
        }

        if (c % d != 0) {
            out<<"0 0\n";
        }
        else {
            out<<x*(c/d)<<' '<<y*(c/d)<<'\n';
        }
    }

    in.close();out.close();
    return 0;
}

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

    ll x0,y0,d;
    d = euclid(b,a%b,x0,y0);
    x = y0;
    y = x0 - y0*(a/b)*b;
    return d;
}