Cod sursa(job #2070125)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 19 noiembrie 2017 11:38:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");

int n, a, b, c, d;

/*void euclid(int a,int b,int *d,int *x,int *y)
{
    if(!b)
    {
        *d=a;
        *x=1;
        *y=0;
    }
    else
    {
        int x0,y0;
        euclid(b,a%b,d,&x0,&y0);
        *x=y0;
        *y=x0-(a/b)*y0;
    }
}*/

int euclid(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = euclid(b,a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
    return gcd;
}

int main()
{
    int x,y;
    f>>n;
    for (;n;--n)
    {
        f>>a>>b>>c;
        d=euclid(a,b,x,y);
        if(c%d)
            g<<"0 0\n";
        else
            g<<x*(c/d)<<" "<<y*(c/d)<<"\n";
    }
    return 0;
}