Cod sursa(job #2494605)

Utilizator alexradu04Radu Alexandru alexradu04 Data 18 noiembrie 2019 10:17:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;
int gcdExtended(int a, int b, int &x, int &y)
{
  if (a == 0)
  {
    x = 0;
    y = 1;
    return b;
  }

  int x1, y1;
  int gcd = gcdExtended(b%a, a, x1, y1);
  x = y1 - (b/a) * x1;
  y = x1;
  return gcd;
}
int main()
{ freopen("euclid3.in","r",stdin);
 freopen("euclid3.out","w",stdout);
  int x, y, a, b, c,n;
  scanf("%d",&n);
  for(int i=1;i<=n;++i)
  {
    scanf("%d %d %d",&a,&b,&c);
    int num=gcdExtended(a,b,x,y);
    if(c%num)
    {
        printf("0 0\n");
    }
    else
    {
        printf("%d %d\n",x*(c/num),y*(c/num));
    }
  }
  return 0;
}