Cod sursa(job #787429)

Utilizator JohnPeterJohn Peter JohnPeter Data 13 septembrie 2012 13:33:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<cstdio>
#include<cassert>

using namespace std;

class xyz{
public:

  xyz(){};

  int x, y, z;

  friend xyz operator %(xyz one, xyz two);

};

xyz operator %(xyz one, xyz two){
  xyz ans;
  int aux = one.z / two.z;

  ans.x = one.x - two.x * aux;
  ans.y = one.y - two.y * aux;
  ans.z = one.z - two.z * aux;

  return ans;
}

class euclid{
private:

    xyz cmmdc(xyz one, xyz two){
      xyz aux;

      while(two.z != 0){
        aux = one;
        one = two;
        two = aux % two;
      }

      return one;
    }

public:

  void solve(){
    assert(freopen("euclid3.in", "r", stdin));
    assert(freopen("euclid3.out", "w", stdout));

    int cases;
    scanf("%d", &cases);

    for(int i = 0; i < cases; ++i){
      xyz one, two, ans;
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);

      if(x == 0 && y == 0)
        printf("0 0\n");

      one.x = 1;
      one.y = 0;
      one.z = x;
      two.x = 0;
      two.y = 1;
      two.z = y;

      ans = cmmdc(one, two);
      //printf("%d %d %d ", ans.x, ans.y, ans.z);

      if(z % ans.z)
        printf("0 0\n");
      else
        printf("%d %d\n",ans.x * (z / ans.z), ans.y * (z / ans.z));

    }

  }

} t;

int main(){
  t.solve();

  return 0;
}