Cod sursa(job #1248226)

Utilizator TrixerAdrian Dinu Trixer Data 24 octombrie 2014 20:01:38
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <assert.h>

using namespace std;

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

int main()
{
    int T;

    ifstream f;
    ofstream g;

    f.open("euclid3.in");
    g.open("euclid3.out");

    for (f>>T,assert(T<=100);T;T--)
    {
        int a,b,c;
        f>>a>>b>>c;

        assert(-1000000000<=a && a<=1000000000);
        assert(-1000000000<=b && b<=1000000000);
        assert(-2000000000<=c && c<=2000000000);

        int d,x,y;
        euclidExtins(a,b,d,x,y);

        if (c%d) g<<"0 0\n";
        else g<<x*c/d<<' '<<y*c/d<<'\n';
    }

    f.close();
    g.close();

    return 0;
}