Cod sursa(job #715843)

Utilizator mytzuskyMihai Morcov mytzusky Data 17 martie 2012 20:42:00
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int euclid_e(int a, int b, int &x, int &y)
{
    if(!b){    x=1;    y=0;    return a;  }
    int x1,y1,c;

    c = euclid_e(b, a%b, x1, y1);

    x = y1;
    y = x1 - (a/b)*y1;

    return c;
}

int main()
{
    freopen ("euclid3.in","r",stdin);
    freopen ("euclid3.out","w",stdout);
    int t,d,x,y;
    int a,b,c;
    scanf("%d", &t);
    for(int i=1;i<=t;++i)
    {
        scanf("%d %d %d", &a, &b, &c);

        d = euclid_e(a,b,x,y);
        if(c%d)
            printf("0 0\n");
        else
        {
            int t = x*(c/d);
            int r = y*(c/d);
            printf("%d %d\n", t,r);
        }
    }
    return 0;
}