Cod sursa(job #1856056)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 ianuarie 2017 14:34:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

pair<ll, ll> euclid_extins(ll x, ll y){
    pair<ll, ll> tmp;
    return x == 0 ? make_pair(0ll, 1ll) :
        (tmp = euclid_extins(y%x, x),
        swap(tmp.first, tmp.second),
        tmp.first -= tmp.second *(y/x),
        tmp); }

int main(){
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");
    int t;
    f >> t;
    for(ll a, b, c; t; --t){
        f >> a >> b >> c;
        const ll d = __gcd(a, b);
        if(c % d != 0) g << "0 0" << '\n';
        else{
            auto p = euclid_extins(a, b);
            g << (c/d) * p.first << ' ' << (c/d) * p.second << '\n'; } }
    return 0; }