Cod sursa(job #1191260)

Utilizator mariusn01Marius Nicoli mariusn01 Data 26 mai 2014 21:28:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

long long a, b, c, t, x, y, d;

long long cmmdc(long long a, long long b) {
    long long r;
    while (b) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void euclid(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
    } else {
        long long x1, y1;
        euclid(b, a%b, x1, y1);
        x = y1;
        y = x1 - a/b*y1;
    }
}

int main() {
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    fin>>t;
    for (;t--;) {
        fin>>a>>b>>c;
        d = cmmdc(a, b);
        if (c%d != 0) {
            fout<<"0 0\n";
            continue;
        }
        euclid(a, b, x, y);
        fout<<c/d*x<<" "<<c/d*y<<"\n";
    }

    return 0;
}