Cod sursa(job #1990493)

Utilizator MaligMamaliga cu smantana Malig Data 12 iunie 2017 09:19:40
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

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

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 5e5 + 5;

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

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

    while (T--) {
        ll a,b,c,x,y;
        bool negA = false,negB = false;

        in>>a>>b>>c;

        if (a < 0) {
            negA = true;
            a = -a;
        }

        if (b < 0) {
            negB = true;
            b = -b;
        }

        ll d = euclid(a,b,x,y);
        if (negA) {
            x = -x;
        }
        if (negB) {
            y = -y;
        }

        //cout<<d<<'\n';
        if (c % d) {
            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 - (a/b)*y0;
    return d;
}