Cod sursa(job #1162070)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 31 martie 2014 16:53:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <iostream>
#include <fstream>
using namespace std;

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

   int v[32];

 void Solve(int a,int b,int res)
 { int n=0,i,x,y,x0,y0,c,d,inita=a,initb=b;

     while(b)
      { n++; v[n]=a/b;
         c=a%b;
        a=b; b=c;
      }
      d=a;

   if (res%d!=0) {g<<"0 0\n"; return;}

    x0=1; y0=0;
     for(i=n;i>=1;i--)
      { x=y0; y=x0-v[i]*y0;
         x0=x; y0=y;
      }
     res/=d;

      g<<x0*res<<" "<<y0*res<<"\n";
 }
int main()
{ int a,b,c,res,t;
   f>>t;

    for(;t;t--)
     { f>>a>>b>>res;
        Solve(a,b,res);
     }

    return 0;
}