Cod sursa(job #2929269)

Utilizator andiRTanasescu Andrei-Rares andiR Data 25 octombrie 2022 14:12:45
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>

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

short t,i;
int a,b,c,cmmdc,x,y;
int gcdext(int a, int b, int &x, int &y){
    int s1=a, s2=b, s3;
    int a1=1, a2=0, a3;
    int b1=0, b2=1, b3;
    while (s2!=0){
        s3=s1%s2;
        a3=a1-(s1/s2)*a2;
        b3=b1-(s1/s2)*b2;
        s1=s2; a1=a2; b1=b2;
        s2=s3; a2=a3; b2=b3;
    }
    x=a1;
    y=b1;
    return s1;
}
int main()
{
    fin>>t;
    for (i=0;i<t;i++){
        fin>>a>>b>>c;
        cmmdc=gcdext(a,b,x,y);
        if (c%cmmdc!=0)
            fout<<"0\n";
        else fout<<x*(c/cmmdc)<<' '<<y*(c/cmmdc)<<'\n';
    }
    return 0;
}