Cod sursa(job #2001356)

Utilizator MaligMamaliga cu smantana Malig Data 16 iulie 2017 14:57:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <stack>
#include <cstring>

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 inf = 1e9 + 5;
const int NMax = 1e7 + 5;
const int nrBytes = 4;
const int bits = 8;
const int Radix = 0b11111111;

int T;

int euclid(int,int,int&,int&);

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

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

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

        int 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;
}

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

    int x0,y0,
    d = euclid(b,a%b,x0,y0);

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