Cod sursa(job #2285224)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 18 noiembrie 2018 12:28:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>

int N;

int euclid_ext(int a, int b, int &x, int &y) {
   if (b == 0) {
      x = 1;
      y = 0;
      return a;
   }
   int x0 = 0;
   int y0 = 0;

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

int main() {
   freopen("euclid3.in", "r", stdin);
   freopen("euclid3.out", "w", stdout);

   scanf("%d", &N);

   while(N--) {
      int a, b, c, d, x, y;
      scanf("%d %d %d", &a, &b, &c);

      d = euclid_ext(a, b, x, y);
      if (c % d) {
         printf("0 0\n");
      } else {
         printf("%d %d\n", x * (c / d), y * (c / d));
      }
   }

   fclose(stdin);
   fclose(stdout);
   return 0;
}