Cod sursa(job #2499047)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 25 noiembrie 2019 10:37:18
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

namespace euclid {
        int gcd(int a, int b) {
                if (a < b) {
                        std::swap(a, b) ;
                }
                while (b) {
                        b ^= a ^= b ^= a %= b ;
                }
                return a ;
        }

        int get_coef(int a, int b, int &x, int &y) {
                if (a == 0) {
                        x = 0 ;
                        y = 1 ;
                        return b ;
                }
                int x1, y1 ;
                get_coef(b % a, a, x1, y1) ;
                x = y1 - (b / a) * x1 ;
                y = x1 ;
                return gcd(a, b) ;
        }

        std::pair<int, int> extended_gcd(int a, int b) {
                int x, y ;
                if (a == b) {
                        return std::make_pair(0, 1) ;
                }
                get_coef(a, b, x, y) ;
                return std::make_pair(x, y) ;
        }
}

int main() {
        freopen("euclid3.in", "r", stdin) ;
        freopen("euclid3.out", "w", stdout) ;
        long long a, b, c ;
        int n ;
        std::cin >> n ;
        for (int i = 1 ; i <= n && std::cin >> a >> b >> c ; ++ i) {
                std::pair<int, int> ext = euclid::extended_gcd(a, b) ;
                int D = euclid::gcd(a, b) ;
                std::cout << ext.first * c << ' ' << ext.second * c << '\n' ;
        }
}