Cod sursa(job #2257299)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 9 octombrie 2018 21:51:25
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

void euclid(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return ;
  }
  int x0 = x;
  int y0 = y;
  euclid(b, a % b, x0, y0);
  int q = a / b;
  x = y0;
  y = x0 - q * x;
}

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

  int t;
  scanf("%d", &t);
  while (t--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    int x, y;
    euclid(a, b, x, y);
    int aux = a * x + b * y;
    if (c % aux != 0)
      printf("0 0\n");
    else
      printf("%d %d\n", x * c / aux, y * c / aux);
  }

  return 0;
}