Cod sursa(job #2655681)

Utilizator sebi_info1Olaru Sebastian sebi_info1 Data 5 octombrie 2020 10:37:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
 
ifstream f("euclid3.in");
ofstream g("euclid3.out");
 
int gcd(int d, int i)
{
    while(i)
    {
        int r = d % i;
        d = i;
        i = r;
    }
    return d;
}
 
int euclid_extins(int a, int b, int &x, int &y)
{
    if(b == 0)
        x = 1, y = 0;
    else
    {
        euclid_extins(b, a % b, x, y);
        int aux = y;
        y = x - (a / b) * y;
        x = aux;
    }
}
 
int main()
{
    int x, y, a, b, c, t, cmmdc, i;
    f >> t;
    for(i = 1; i <= t; ++ i)
    {
        f >> a >> b >> c;
        cmmdc = gcd(a, b);
        if(c % cmmdc != 0)
            g << "0" << " " << "0" << "\n";
        else
        {
            euclid_extins(a, b, x, y);
            g << x * (c / cmmdc) << " " << y * (c / cmmdc) << "\n";
        }
    }
    return 0;
}