Cod sursa(job #1235615)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 30 septembrie 2014 03:18:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>

#define pb push_back

#define mp make_pair
#define f first
#define s second
#define ll long long

using namespace std;

int main() {
  ifstream cin("euclid3.in");
  ofstream cout("euclid3.out");

  int T; cin >> T;
  while(T--) {
    int A, B, C;
    cin >> A >> B >> C;

    if (C % __gcd(A, B)) {
      cout << "0 0\n";
    } else if(A == 0 && B == 0) {
      cout << "0 0\n";
    }else {

      //a * new_s + b * new_t = gcd(a, b)
      //s[i + 1] = s[i - 1] - s[i] * q[i]
      //t[i + 1] = t[i - 1] - t[i] * q[i]
      int old_s = 1, new_s = 0;
      int old_t = 0, new_t = 1;

      int a = A, b = B;
      while(b != 0) {
        int save;
        int r = a % b, q = a / b;

        save = new_s;
        new_s = old_s - new_s * q;
        old_s = save;

        save = new_t;
        new_t = old_t - new_t * q;
        old_t = save;

        a = b; b = r;
      }

      cout << old_s * (C / a) << " " << old_t * (C/a) << "\n";
    }
  }
  return 0;
}