Cod sursa(job #3295990)

Utilizator Lex._.Lexi Guiman Lex._. Data 10 mai 2025 14:47:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;

int euclid_extins(int a, int b, int& x1, int& y1) //algoritmul lui euclid extins pentru a afla x1 si y1 astfel incat a*x1+b*y1=(a, b)
{
    if(b==0)
    {
        x1=1;
        y1=0;
        return a; //returnam cmmdc-ul numerelor
    }
    int x2, y2;
    int d=euclid_extins(b, a%b, x2, y2);
    x1=y2;
    y1=x2-a/b*y2;
    return d; //returnam cmmdc-ul numerelor
}

int main()
{
    ifstream cin("euclid3.in");
    ofstream cout("euclid3.out");
    int t;
    cin >> t;
    while(t--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int x1, y1; //numerele pentru care a*x1+b*y1=(a, b), unde (a, b) este cmmdc-ul lui a si b
        int d=euclid_extins(a, b, x1, y1); //cmmdc-ul lui a si b
        if(c%d==0) //daca c este divizibil cu d, atunci exista o solutie pentru ecuatie
        {
            int factor=c/d; //factorul cu care se inmulteste toata ecuatia a*x1+b*y1=d
            cout << factor*x1 << " " << factor*y1 << "\n";
        }
        else //daca nu, atunci nu exista nici-o solutie in numerele intregi
        {
            cout << 0 << " " << 0 << "\n";
        }
    }

    return 0;
}