Cod sursa(job #1089520)

Utilizator kiralalaChitoraga Dumitru kiralala Data 21 ianuarie 2014 19:02:43
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

FILE* f=freopen("euclid3.in","r",stdin);
FILE* o=freopen("euclid3.out","w",stdout);

int a,b,c,n;

void Euclid(int a, int b, int *cmmdc, int &x1, int &y1)
{
    if(b==0)
    {
        *cmmdc=a;
        x1=1;
        y1=0;
    }
    else
    {
        int x0,y0;
        Euclid(b,a%b,cmmdc,x0,y0);
        x1=y0;
        y1=x0-(a/b)*y0;
    }
}

void ComputeAnswer(int &x, int &y)
{
    int x1,y1;
    int cmmdc;
    Euclid(a,b,&cmmdc,x1,y1);
    if(c%cmmdc!=0) x=y=0;
    else
    {
        x=x1*c/cmmdc;
        y=y1*c/cmmdc;
    }
}

int main()
{
    int x,y;
    scanf("%d",&n);

    for(int i=0;i<n;++i)
    {
        scanf("%d%d%d",&a,&b,&c);

        ComputeAnswer(x,y);

        printf("%d %d\n",x,y);
    }

    return 0;
}