Cod sursa(job #1973779)

Utilizator MaligMamaliga cu smantana Malig Data 25 aprilie 2017 21:42:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

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

#define ll long long

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

int main() {

    /*
    int v1,v2,v3;
    v1 = 413693251811;
    v2 = 2803244933575;
    v3 = v1+v2;
    cout<<v3<<'\n';
    */


    int T;
    in>>T;

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

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

        ll x,y,gcd;
        gcd = euclid(a,b,x,y);
        if (c % gcd != 0) {
            out<<"0 0\n";
        }
        else {
            if (minusA) {
                x = -x;
            }
            if (minusB) {
                y = -y;
            }

            out<<x * c/gcd<<' '<<y * c/gcd<<'\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;
}