Cod sursa(job #1202735)

Utilizator pentrusandaPentru Sanda pentrusanda Data 29 iunie 2014 13:12:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>

using namespace std;

int a,b,c,v1,v2,t;

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

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

    in>>t;
    for (;t>0;--t)
    {
        in>>a>>b>>c;
        int x=a,y=b;
        while (y!=0)
        {
            int v=x;
            x=y;
            y=v%y;
        }
        if (c%x!=0)
        {
            out<<"0 0\n";
        }else
        {
            int v1,v2;
            calc(a,b,x,v1,v2);
            out<<c/x*v1<<" "<<c/x*v2<<"\n";
        }
    }

    in.close();
    out.close();
    return 0;
}