Cod sursa(job #997941)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 15 septembrie 2013 11:43:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

class obj{
public:
  int x, y, ans;

  obj(){};

  obj(int a, int b, int c){
    x = a;
    y = b;
    ans = c;
  }

  obj operator * (int other){
    obj we(x * other, y * other, ans * other);
    return we;
  }

  obj operator -(obj other){
    obj we(x - other.x, y - other.y, ans - other.ans);
    return we;
  }
};

obj gcd(obj x, obj y){
  obj z;
  while(y.ans){
    z = x;
    x = y;
    y = z - y * (z.ans / y.ans);
  }
  return x;
}

int main(){
  ifstream in("euclid3.in");
  ofstream out("euclid3.out");

  int t;
  in >> t;
  while(t--){
    int a, b, c;
    in >> a >> b >> c;
    obj one(1, 0, a), two(0, 1, b);
    obj three = gcd(one, two);
    if(c % three.ans)
      out << "0 0\n";
    else
      out << three.x * (c / three.ans) << " " << three.y * (c / three.ans) << "\n";
  }

  return 0;
}