Cod sursa(job #3253759)

Utilizator mariusharabariMarius Harabari mariusharabari Data 4 noiembrie 2024 18:41:50
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

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

long long int T, A, B, C, i, X, Y, D;

void euclid(long long int a, long long int b, long long int &x, long long int &y, long long int &d){
    if(b==0){
        d=a;
        x=y=1;
    }
    else{
        long long int x1, y1;
        euclid(b, a%b, x1, y1,d);
        x=y1;
        y=x1-a/b*y1;
    }
}

int main(){
    fin>>T;
    for(i=1;i<=T;i++){
        fin>>A>>B>>C;
        euclid(A, B, X, Y, D);
        X*=C/D;
        Y*=C/D;
        if(C%D==0)
            fout<<X<<" "<<Y<<endl;
        else
            fout<<0<<" "<<0<<endl;
    }
    return 0;
}