Cod sursa(job #3223364)

Utilizator andrei_botorogeanuBotorogeanu Andrei andrei_botorogeanu Data 13 aprilie 2024 11:01:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include<iostream>
#define FIN "euclid3.in"
#define FOUT "euclid3.out"
using namespace std;
void euclid_extented(int a, int b, int *d, int *x, int *y)
{
  if(b == 0) {
    *d = a;
    *x = 1;
    *y = 0;
  } else {
    int x1, y1;
    euclid_extented(b, a%b, d, &x1, &y1);
    *x = y1;
    *y = x1 - (a/b)*y1;
  }
}
int main()
{
  int x, y, d, a, b, c, T;
  freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);
  scanf("%d", &T);
  while(T--) {
    scanf("%d %d %d", &a, &b, &c);
    int d, x, y;
    euclid_extented(a, b, &d, &x, &y);
    if(c % d != 0) {
      printf("%d %d\n", 0, 0);
    } else {
    printf("%d %d\n", (c/d)*x, (c/d)*y);
    }
  }
}