Cod sursa(job #2309084)

Utilizator CoroloHorjea Cosmin Corolo Data 28 decembrie 2018 13:57:12
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int euclid(int a,int b){
      int r;
      while(a && b){
            if(a>b){
                  a=a%b;
            }
            else{ 
                  b=b%a;
            }
            
      }
      return  a ? a: b;
}

void rezolv(int a,int b,int *d,int *x,int *y)
{
      if(b==0)
      {
            *d=a;
            *x=1;
            *y=0;
      }else{
            int x0,y0;
            rezolv(b,a%b,d,&x0,&y0);
            *x=y0;
            *y=x0-(a-b)*y0;
      }
}

int main(){
      int n,a,b,T,c;
      f>>T;
      for(int i = 0;i<T;i++)
      {
            f>>a>>b>>c;
            int d = euclid(a,b);
            if(c%d!=0)g<<"0 0\n";
            else {
                 int x,y,d;
                 rezolv(a,b,&d,&x,&y);
                 g<<x<<" "<<y<<'\n'; 
            }
      }
      g.close();
      f.close();
}