Cod sursa(job #2337747)

Utilizator ewaldBerla Ewald ewald Data 6 februarie 2019 18:06:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int ext_gcd(int a, int b, int & x, int & y){
   if( !b ){
    x=1;
    y=0;
    return a;
   }else{
   int x1, y1;
   int result = ext_gcd(b, a%b, x1, y1);
   x= y1;
   y= x1 - y1* (a/b);
   return result;
   }
}

int main(){
    int n;
    f>>n;
    while(n--){
            int x,y,gcd,c,a,b;
            f>>a>>b>>c;
            gcd = ext_gcd(a,b,x,y);
            if(c%gcd)
                g<<0<<" "<<0<<"\n";
            else g<<1LL*x*c/gcd<<" "<<1LL*y*c/gcd<<"\n";

    }
}