Cod sursa(job #1066115)

Utilizator cruelifanLouis Cypher cruelifan Data 24 decembrie 2013 00:32:43
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

using namespace std;

class eq{
public:
  long long a, b, res;

  eq(){};

  eq(long long a1, long long b1, long long res1){
    a = a1;
    b = b1;
    res = res1;
  }

  eq operator %(eq other){
    long long t = res / other.res;
    eq ans(a - t * other.a, b - t* other.b, res % other.res);
    return ans;
  }
};

eq gcd(eq x, eq y){
  eq z;
  while(y.res){
    z = x;
    x = y;
    y = z % y;
  }
  return x;
}

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

  long long t;
  in >> t;
  while(t--){
    long long x, y, z;
    in >> x >> y >> z;
    eq a(x, 0, x), b(0, y, y);
    eq ans = gcd(a, b);

    if(z % ans.res != 0){
      out << "0 0 \n";
      continue;
    }

    out << ans.a / x * z / ans.res << " " << ans.b / y * z / ans.res << "\n";
  }

  return 0;
}