Cod sursa(job #2221299)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 13 iulie 2018 17:19:00
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

long long int cmmdc(long long int a, long long int b)
{
  if(a == 0)
    return b;
  if(b == 0)
    return a;
  if(a < b)
    return cmmdc(b, a);
  return cmmdc(a % b, b);
}

void solve()
{
  long long int a, b, c;
  scanf("%lld", &a);
  scanf("%lld", &b);
  scanf("%lld", &c);
  long long int ax = abs(a);
  long long int by = abs(b);
  long long int d = cmmdc(ax, by);
  if(c % d != 0)
  {
    printf("0 0\n");
    return;
  }
  while(abs(ax - by) != d)
  {
    if(ax > by)
    {
      by += ((ax - by) / b + 1) * b;
    }
    else
    {
      ax += ((by - ax) / a + 1) * a;
    }
  }
  if(a < 0)
    ax = -ax;
  if(b < 0)
    by = -by;
  if(ax - by == -d)
  {
    ax = -ax;
    by = -by;
  }
  long long int x = ax / a;
  long long int y = -by / b;
  long long int deCateOriIntra = c / d;
  x *= deCateOriIntra;
  y *= deCateOriIntra;
  printf("%lld %lld\n", x, y);
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    int t;
    scanf("%d", &t);
    for(int test = 0; test < t; ++test)
    {
      solve();
    }
    return 0;
}