Cod sursa(job #1465875)

Utilizator DoraBenzoVelicu Teodora DoraBenzo Data 28 iulie 2015 10:32:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int kt[100];

void euclid(int &a, int b, int &k)
{
    while(b)
    {
        int r;
        r = a % b;
        kt[++k]=a/b;
        a = b;
        b = r;
    }
}

void solutii(int &a, int &b, int k)
{
    int i, x = 1, y = 0;
    a=x;b=y;
    for(i=k; i>=1; i--)
    {
        a = y;
        b = x - y * kt[i];
        x = a;
        y = b;
    }
}

int main()
{
    int n, a, b, c, k;

    fin >> n;
    while(n)
    {
        fin >> a >> b >> c;
        k = 0;
        euclid(a, b, k);
        if(c % a != 0)
            fout<<"0 0"<<"\n";
        else
        {
            int x=0, y=0, d;
            d = c / a;
            solutii(x, y, k);
            fout<<x*d<<" "<<y*d<<"\n";
        }
        n --;
    }

    return 0;
}