Cod sursa(job #3132318)

Utilizator mihai2387648Constantin Mihai mihai2387648 Data 22 mai 2023 04:34:15
Problema Algoritmul lui Euclid extins Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>

int extendedEuclidean(int a, int m, int* x, int* y) {
    int x1,y1,gcd;

    if (a == 0) {
        *x = 0;
        *y = 1;
        return m;
    }

    gcd = extendedEuclidean(m % a, a, &x1, &y1);
    *x = y1 - (m / a) * x1;
    *y = x1;

    return gcd;
}

int main() {
    int a,b,c,t,i=0;
    int x,y;

    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d" , &t);

    while(i<t && scanf("%d %d %d" ,&a,&b,&c) == 3){
        int d = extendedEuclidean(a,b,&x,&y);
        if(c%d==0){
            printf("%d %d" , x*(c/d) , y*(c/d));
        }
        else
            printf("0 0");
        i++;
    }

    //printf("%d",reverseModulo(a,m));

    return 0;
}