Cod sursa(job #1673936)

Utilizator martonsSoos Marton martons Data 4 aprilie 2016 11:25:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>

using namespace std;

int cmmdc(int a, int b){
    int t;
    if(a<b){
        t=a;
        a=b;
        b=t;
    }

    while(b){
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}

void rez(int a, int b, int c, int &x, int &y){
    int t, v[50]={0}, i=0;

    while(b){
        v[i++]=a/b;
        t=b;
        b=a%b;
        a=t;
    }
    int x0=c/a,y0=0;

    while(i>0){
        i--;
        x=y0;
        y=x0-v[i]*y0;
        x0=x;
        y0=y;
    }
}

int main()
{
    FILE* f=fopen("euclid3.in", "r");
    FILE* f1=fopen("euclid3.out", "w");
    int t;
    fscanf(f, "%d", &t);

    while(t){
        t--;
        int a, b, c, d;
        fscanf(f, "%d%d%d", &a, &b, &c);
        d=cmmdc(a, b);

        if(c%d!=0){
            fprintf(f1, "0 0\n");
        }
        else{
            int x, y;
            rez(a, b, c, x, y);
            fprintf(f1, "%d %d\n", x, y);
        }
    }
    return 0;
}