Cod sursa(job #2674648)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 19 noiembrie 2020 19:19:51
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <cstring>
#include <cstring>
#define MOD 1234

using namespace std ;

ifstream cin ("euclid3.in") ;
ofstream cout ("euclid3.out") ;
/*
int frecv[509] ;

unsigned long long fact(int n)
{

    unsigned long long aux = 1 ;

    for(int f = 2 ; f <= n ; f ++)
        aux *= f ;

    return aux ;

}

int main()
{

    string a ;

    cin >> a ;

    for(int f = 0 ; f < a.size() ; f ++)
        frecv[a[f]] ++ ;

    int n = a.size(), ok = 0 ;

    for(int f = 0 ; f <= 500 ; f ++)
    {

        if(ok && frecv[f] % 2)
        {

            cout << 0 ;

            return 0 ;

        }

        if(frecv[f] % 2)frecv[f] --, n --, ok = 1 ;

        frecv[f] /= 2 ;

    }

    unsigned long long sus = fact(n / 2), jos = 1 ;

    for(int f = 2 ; f <= 500 ; f ++)
        if(frecv[f])jos *= fact(frecv[f]), jos %= MOD ;

    cout << sus / jos ;

    return 0 ;

}
*/

pair<long long, long long> e_extins(long x, long long y)
{

    if(y == 0)return {1, 0} ;

    pair<long long, long long> aux = e_extins(y, x % y) ;

    return {aux.second, aux.first - aux.second * (x / y)} ;

}

int main()
{

    int n ;

    cin >> n ;

    for(int f = 1 ; f <= n ; f ++)
    {

        long long a, b, c ;

        cin >> a >> b >> c ;

        int d = __gcd(a, b) ;

        if(c % d)
        {

            cout << 0 << " " << 0 ;

        }
        else
        {

            a *= c / d ;
            b *= c / d ;

            pair<long long, long long> aux = e_extins(a, b) ;

            aux.first *= c / d ;
            aux.second *= c / d ;

            cout << aux.first << " " << aux.second << '\n' ;

        }

    }

    return 0 ;

}