Cod sursa(job #2089863)

Utilizator PetyAlexandru Peticaru Pety Data 17 decembrie 2017 12:11:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
int n, a, b, c, x, y, d;
void euclid (int a, int b, int &d, int &x0, int &y0){
  x0 = 1, y0 = 0;
  int x1 = 0, y1 = 1, x, y;
  while (b != 0) {
    int cat = a / b;
    int r = a % b;
    a = b;
    b = r;
    x = x0 - x1 * cat;
    y = y0 - y1 * cat;
    x0 = x1;
    x1 = x;
    y0 = y1;
    y1 = y;
  }
  d = a;
}
int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
      fin >> a >> b >> c;
      euclid (a, b, d, x, y);
      if (c % d != 0)
        fout << "0 0\n";
      else {
        int k = c / d;
        x *= k;
        y *= k;
        fout << x << " " << y << "\n";
      }
    }
    return 0;
}