Cod sursa(job #2649422)

Utilizator Rares31100Popa Rares Rares31100 Data 14 septembrie 2020 17:39:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("euclid3.in");
ofstream out("euclid3.out");
int t, a, b, rez;

long long cmmdc(long long a, long long b)
{
    a = abs(a);
    b = abs(b);
    int rest;

    while(b)
    {
        rest = a%b;
        a = b;
        b = rest;
    }

    return a;
}

void findSol(int a, int b, long long &x, long long &y)
{
    if(b == 0)
    {
        x = rez / a;
        y = 0;
        return;
    }

    findSol(b, a%b, x, y);
    x = y;
    y = (rez - a * x) / b;
}

int main()
{
    in >> t;

    while(t--)
    {
        in >> a >> b >> rez;
        long long x, y;

        if( rez % cmmdc(a, b) == 0 )
        {
            findSol(a, b, x, y);
            out << x << ' ' << y << '\n';
        }
        else
            out << "0 0\n";
    }

    return 0;
}