Cod sursa(job #1278178)

Utilizator tudorcomanTudor Coman tudorcoman Data 28 noiembrie 2014 16:41:50
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>

using namespace std;


long long T, i, a, b, c, 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 x0,y0;
    euclid(b, a % b , x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
    }
}
int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d",&T);
    for(i = 1; i <= T; i ++){
        scanf("%lld%lld%lld",&a,&b,&c); // citire
    D = cmmdc(a,b); // cmmdc
    if( c % D != 0) // daca c nu se imparte la cmmdc
        printf("0 0\n");
    else{
        euclid(a,b,x,y);// aplicam algoritmu extins
        printf("%lld %lld\n",x*(c/D),y*(c/D)); //  af rez
        }
    }

    return 0;
}