Cod sursa(job #3308804)

Utilizator andrei.nNemtisor Andrei andrei.n Data 28 august 2025 12:47:22
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;

pair<int,int> euclid(int a, int b)
{
    int x1 = 1, y1 = 0;
    int x2 = 0, y2 = 1;
    int x3, y3;
    while(b)
    {
        x3 = x1 - x2 * (a / b);
        y3 = y1 - y2 * (a / b);
        x1 = x2; y1 = y2;
        x2 = x3; y2 = y3;
        int r = a % b;
        a = b;
        b = r;
    }
    return {x1, y1};
}

signed main()
{
    ifstream fin ("euclid3.in");
    ofstream fout ("euclid3.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int T; fin>>T; while(T--)
    {
        int a,b,c; fin>>a>>b>>c;
        int d = __gcd(a,b), r;
        if(c%d)
        {
            fout<<"0 0\n";
            continue;
        }
        a /= d; b /= d; c /= d;
        auto [x, y] = euclid(a, b);
        fout << x * c << ' ' << y * c << '\n';
    }
    return 0;
}