Cod sursa(job #3291970)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 6 aprilie 2025 16:51:04
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
// 100 Puncte
#include <bits/stdc++.h>

using namespace std;

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

int xp, xc, xf, yp, yc, yf, iter;

int gcd (int a, int b) {
    iter++;
    if (b==0) {
        return a;
    }
    else {
        int q = a/b;
        xf = xp - q*xc;
        yf = yp - q*yc;
        xp = xc; yp = yc;
        xc = xf; yc = yf;
        int d = gcd(b, a % b);
        // cout<<a<<'*'<<xp<<'+'<<b<<'*'<<yp<<'='<<d<<endl;
        return d;
    }
}

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int t; fin>>t;
    while (t--) {
        int a, b, c; fin>>a>>b>>c;

        xp=1; xc=0; 
        yp=0; yc=1;
        iter = 0;

        int d = gcd(a, b);
        // cout<<endl;
        int x = xf, y = yf;
        int rap = c / d;
        if (c%d!=0) {
            fout<<"0 0\n";
            continue;
        }
        else {
            x*=rap; y*=rap;
            fout<<x<<' '<<y<<'\n';
        }
    }
    return 0;
}