Cod sursa(job #329654)

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

entry ext(ll A,ll 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];
      
      int i = 2;
      for(ll t0 = A, t1 = B ; t0 % t1; ++i) {
                             
                             ll 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--) {
                   
             ll 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;
}