Cod sursa(job #1307952)

Utilizator viuscenkoViktor Iuscenko viuscenko Data 3 ianuarie 2015 03:38:23
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.93 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <fstream>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <string>
#include <cassert>

using namespace std;
typedef long long               LL;
typedef vector<int>             vi;
typedef vector<vi>              vii;
typedef pair<int,int>           pii;
typedef pair<int, pii>          piii;
typedef pair<LL, int>           pLLii;
typedef pair<int, LL>           piiLL;
typedef pair<LL,  LL>           pLLLL;
typedef pair<double, double>    pdd;

#define     For(i,a,b)      for(int i=a;i<=b;++i)
#define     rFor(i,a,b)     for(int i=a;i>=b;--i)
#define     Rep(i,a)        for(int i=0; i<a; ++i)
#define     iRep(i,a)       for(int i=a; i>=0; --i)
#define     fore(x,i)       for(__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define     rfore(x,i)      for(__typeof((x).rbegin()) i=(x).rbegin(); i!=(x).rend(); ++i)
#define     dforup(i,a,b)   for(i=a; i<b; ++i)
#define     dfordn(i,a,b)   for(i=a; i>b; --i)
#define     drep(i,a)       for(i=0; i<a; ++i)

#define     slenn(s,n)      for(n=0; s[n]!='\0'; ++n)

#define     MAX(a,b)        (((a) > (b)) ? (a) : (b))
#define     MIN(a,b)        (((a) < (b)) ? (a) : (b))
#define     last(a)         int(a.size() - 1)

#define     gl(x)           cin>>x
#define     gr(x)           fin>>x

#define     pls(x)          cout<<x<<" "
#define     plsr(x)         fout<<x<<" "
#define     pln(x)          cout<<x<<"\n"
#define     plnr(x)         fout<<x<<"\n"

#define     mem(a,b)        memset(a,b,sizeof(a))
#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     clr(a)          a.clear()
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     all(a)          a.begin(),a.end()
#define     allr(a)         a.rbegin(),a.rend()
#define     full(a,l)       a,a+l
#define     rin(a)          ifstream fin(a)
#define     rout(a)         ofstream fout(a);
#define     rclose()        fin.close(); fout.close();
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

rin("euclid3.in");
rout("euclid3.out");

int ni() { int a; gr(a); return a; }
double nf() { double a; gr(a); return a; }
long long nll() { long long a; gr(a); return a; }

int T, t, a, b, c, d;

inline int euclid(int a, int b)
{
    if(b != 0)
        return euclid(b, a%b);
    else
        return a;
}

void euclidExtins(int a, int b, int &c, int &x, int &y)
{
    if(b == 0)
    {
        c = a;
        x = 1;
        y = 0;
    }
    else
    {
        int x0, y0;
        euclidExtins(b, a%b, c, x0, y0);
        x = y0;
        y = x0 - (a/b) * x;
    }
}

void solve()
{
    a = ni(); b = ni(); c = ni(); D(pln("Reading a,b,c"););
    d = euclid(a, b);
    if (b == 0)
    {
        if (c%a == 0)
        {
        	plnr(c/a << " " << 0);
        }
        else
        {
        	plnr("0 0");
        }
    }
    else
        if( c % d )
            plnr("0 0");
        else
        {
            int x, y;
            euclidExtins(a, b, d, x, y);
            plnr(x * (c/d) << " " << y * (c/d));
        }
}

int main()
{
    T = ni();
    iRep(t, --T)
    {
        D(pln("Solving test nr " << t+1););
        solve();
    }


    rclose();
    return 0;
}