Cod sursa(job #2940261)

Utilizator staicumateiStaicu Matei Octavian staicumatei Data 15 noiembrie 2022 09:59:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

void euclid_extins(int a, int b, int &d, int &x, int &y)
{
    if (b == 0)
    {
        d = a;
        x = 1;
        y = 0;
        return;
    }
    int q = a / b, x_, y_;
    euclid_extins(b, a - q * b, d, x_, y_);
    x = y_;
    y = x_ - q * y_;
}

int main()
{
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");
    int t;
    f>>t;
    for (int i = 0; i < t; i++)
    {
        int a, b, c, d, x, y;
        f >> a >> b >> c;
        euclid_extins(a, b, d, x, y);
        if (c % d == 0)
        {
            int q = c / d;
            g << x * q << " " << y * q <<endl;
        }
        else
        {
            g << "0 0"<<endl;
        }
    }
    return 0;
}