Cod sursa(job #3331941)

Utilizator traian_Dobrescu Traian traian_ Data 1 ianuarie 2026 23:49:00
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <numeric>
#include "stdio.h"
using namespace std;

#define ll long long
const int inf = 0x3f3f3f3f;

int euclid(int a, int b, int&x, int&y) {
    if(b==0) {
        x = 1;
        y = 0;
        return a;
    }
    int x0, y0;
    int ret = euclid(b, a%b, x0, y0);
    x = y0;
    y = x0 - (a/b)*y0;
    return ret;
}

void solve() {
    int a, b, c, x, y;
    cin >> a >> b >> c;
    int d = gcd(a, b);
    if(c/d*d != c) {
        cout << "0 0\n";
        return;
    } 
    euclid(a,b,x,y);
    
    cout << x*(c/d) << " " << y*(c/d) << "\n";
}

int main() {
    #ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    #ifdef  INFOARENA
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    #endif  //INFOARENA

    int t;
    cin >> t;
    for(int i=0;i<t;i++) {
        solve();
    }
}