Cod sursa(job #2864732)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 8 martie 2022 10:23:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int n;
int euclid(int a, int b, int &x, int &y) {
   if (b == 0) {
      x = 1;
      y = 0;
      return a;
   }

   int d, x0, y0;
   d = euclid(b, a % b, x0, y0);
   x = y0;
   y = x0 - (a / b) * y0;

   return d;
}

int main()
{
    fin >> n;
    while(n--) {
      int a, b, c;
      fin >> a >> b >> c;
      int x, y, d;
      d = euclid(a, b, x, y);

      if (c % d)
         fout << 0 << ' ' << 0 <<'\n';
      else
         fout << x * (c / d) << ' ' << y * (c / d) <<'\n';
    }
    return 0;
}