Cod sursa(job #1439586)

Utilizator GeiGeiGeorge Cioroiu GeiGei Data 22 mai 2015 18:48:44
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
//001
#include <cstdio>

void gcd(long a, long b, long& d, long& x, long& y) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        long x0, y0;
        gcd(b, a % b, d, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }
}

void egcd(long a, long b, long& d, long& x, long& y) {
    long s = 0, old_s = 1, t = 1, old_t = 0, r = b, old_r = a;

    while (r != 0) {
        long cat = old_r / r;

        long aux = old_r;
        old_r = r;
        r = aux - cat * r;

        aux = old_s;
        old_s = s;
        s = aux - cat * s;

        aux = old_t;
        old_t = t;
        t = aux - cat * t;
    }

 //   printf("%d %d %d\n", r, s, t);
  //  printf("%d %d %d\n\n", old_r, old_s, old_t);
}

int main() {
    FILE* fi = fopen("euclid2.in", "rt");
    FILE* fo = fopen("euclid.out", "wt");

    int totaltest;
    fscanf(fi, "%d", &totaltest);

    for (int test = 1; test <= totaltest; test++) {
        long a, b, c, x, y, d;
        fscanf(fi, "%ld%ld%ld", &a, &b, &c);
        gcd(a, b, d, x, y);
       // printf("%d\n", d);
        if (c % d == 0)
            fprintf(fo, "%ld %ld\n", (c / d) * x, (c / d) * y);
        else
            fprintf(fo, "0 0\n");
    }

    return 0;
}