Cod sursa(job #889112)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 24 februarie 2013 12:46:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>

typedef struct {
    int p, q;
} pair;

int euclid_extins(int a, int b, int *p, int *q) {
    pair Va, Vb, Vaux;
    Va.p = 1;
    Va.q = 0;
    
    Vb.p = 0;
    Vb.q = 1;

    while(b!=0) {
        int q = a/b, r = a%b;
        a = b; b = r;

        Vaux.p = Va.p; Vaux.q = Va.q;
        Va.p = Vb.p; Va.q = Vb.q;
        //Vb = Va-qVb
        Vb.p = Vaux.p - q*Vb.p;
        Vb.q = Vaux.q - q*Vb.q;
    }

    *p = Va.p;
    *q = Va.q;

    return a;
}

int main() {
    
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    int t, a, b, c, gcd;
    int p, q;

    scanf("%d", &t);

    for(; t>0; t--) {
        scanf("%d%d%d", &a, &b, &c);
        gcd = euclid_extins(a, b, &p, &q);
        //printf("\t%d %d %d\n", gcd, p, q);
        if( c%gcd!=0 ) {
            printf("0 0\n");
        }
        else {
            int cc = c/gcd;
            printf("%d %d\n", p*cc, q*cc);
        }
    }

    return 0;
}