Cod sursa(job #3240308)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 14 august 2024 00:38:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include<bits/stdc++.h>
using namespace std;

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

int64_t t, A, B, C;

int64_t MODINVERSE(int64_t a, int64_t b, int64_t& x, int64_t& y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    else{
        int64_t newX, newY;
        int64_t d = MODINVERSE(b, a % b, newX, newY);
        x = newY;
        y = newX - (a / b) * newY;
        return d;
    }
}

int main(){
    fin >> t;

    for(;t--;){
        fin >> A >> B >> C;

        int64_t x, y;
        int d = MODINVERSE(A, B, x, y);

        if(C % d)
            fout << "0 0\n";
        else
            fout << x * (C / d) << ' ' << y * (C / d) << '\n';
    }
}