Cod sursa(job #329653)

Utilizator mika17Mihai Alex Ionescu mika17 Data 7 iulie 2009 00:13:39
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
using namespace std;
 
struct entry {
      int x,y,d; 
      entry(int xx,int yy,int dd) : x(xx), y(yy), d(dd) {} 
};

entry ext(int A,int B) {
       
      vector < entry > E;
   
      E . push_back ( entry(1,0,A) ); E . push_back( entry(0,1,B) );
      
      if(!A) return E[1]; if(!B) return E[0];
      
      for(int t0 = A, t1 = B, i = 2; t0 % t1; ++i) {
                             
                             int q=E[i-2].d / E[i-1].d,
                              xx = E[i-2].x - E[i-1].x * q, 
                              yy = E[i-2].y - E[i-1].y * q,
                              dd = E[i-2].d % E[i-1].d;
                             
                             t0 = E[i-1].d, t1 = dd;
                             E . push_back( entry(xx,yy,dd) );
      }
             
      return E.back();
}


int main() {
    
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    
    int T;
    fin >> T;
    while(T--) {
                   
             int A,B,C;
             fin >> A >> B >> C; // ax + by = c
             
             entry t = ext(A,B);
             
             if(C % t.d) fout << "0 0\n";
              else  { //fout << t .x << ' ' << t . y << ' ' << t. d << endl;
                    fout << t . x * C / t.d << ' ' << t . y * C / t.d << '\n'; }
    }
             
    return 0;
}