Cod sursa(job #3292016)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 6 aprilie 2025 20:18:55
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

void Algoritmul_lui_Euclid_Extins(int a,int b,int &c,int &x,int &y){
    if (b==0){
        c = a;
        x = 1;
        y = 0;
    }else{
        int nx,ny;
        Algoritmul_lui_Euclid_Extins(b,a%b,c,nx,ny);
        x = ny;
        y = nx-(a/b)*ny;
    }
    return;
}

int Algoritmul_lui_Euclid(int a,int b){
    int c;
    while (b){
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}

signed main()
{
    int t;
    fin >> t;
    while (t--){
        int a,b,c;
        fin >> a >> b >> c;
        int d = Algoritmul_lui_Euclid(a,b);
        if (c%d!=0) fout << "0 0\n";
        else{
            int x,y;
            a *= c/d;
            b *= c/d;
            c *= c/d;
            Algoritmul_lui_Euclid_Extins(a,b,d,x,y);
            fout << x << ' ' << y << '\n';
        }
    }
    return 0;
}