Cod sursa(job #1892627)

Utilizator dago28Stoican Dragos dago28 Data 25 februarie 2017 10:21:21
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <cstdio>

using namespace std;


int n,k,l;


int Euclid(int a, int b)
{
    if (b == 0)
        return a;
    else
        return Euclid(b, a % b);
}


void EuclidExtins (int a, int b, int &k, int &l)
{
    if (b==0)
        k=1,l=1;
    else
    {
        int kp,lp;
        EuclidExtins(b,a%b,kp,lp);
        k=lp;
        l=kp-lp*a/b;
    }
}



int main()
{
    freopen("date.in","r",stdin);
    scanf("%d",&n);
    int a,b,c,cmmdc;
    for (int i=0; i<n; i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        int d=Euclid(a,b);
        if (c%d!=0)
            cout<<0<<" "<<0<<endl;
        else
        {
            EuclidExtins(a,b,k,l);
            cout<<k*(c/d)<<" "<<l*(c/d)<<endl;
        }
    }
    return 0;
}