Cod sursa(job #1781599)

Utilizator sulzandreiandrei sulzandrei Data 17 octombrie 2016 00:37:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
//http://www.infoarena.ro/algoritmul-lui-euclid#comentarii
//http://www.infoarena.ro/problema/euclid3
#include <fstream>
#include <tuple>
#define ull long long int
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
void euclidExtins(ull  a, ull b , ull *d, ull *x, ull *y)//a,b numerele noastre , d va fi gcd(a,b)
{
    if(b == 0)//daca b= 0 atunc gcd(a,b) = a = *d deci putem lua x = 1 si y = 0 atunci a*1 + b*0 = a
    {
        *x = 1;
        *y = 0;
        *d = a;
    }
    else
    {
        ull x0,y0;//calculam in x0 si y0(x si y) pentru b si a%b
        euclidExtins(b, a%b, d, &x0, &y0);
        // b * x0 + a%b * y0 = d si d = a * x + b * y deci
        //daca scriem a % b = a - b * c unde c = a/b
        //avem b * (x0 - c * y0 - y) = a * (x - y0) si putem lua
        //x0 - c * y0 - y = 0 deci y = x0 -c * y0(prin prelucrari)
        //si x -y0 = 0 deci x = y0
        *x = y0;
        *y = x0 - (a/b) * y0;
    }
}
tuple<int,int,int> extendedEuclid(int a, int b)//versiunea 2
{
    if (b == 0)
        return std::make_tuple(a,1,0);
    tuple<int,int,int> dxyp = extendedEuclid(b,a%b);
    int xp = get<1>(dxyp);
    int yp = get<2>(dxyp);
    int dp = get<0>(dxyp);
    return std::make_tuple(dp,yp,xp- (a/b)*yp);
}
int main()
{
    ull x,y,a,b,c,d,t,i;
    in >> t;
    for( i = 0 ; i < t ; i++)
    {
        in >> a >> b >> c;
        //euclidExtins(a, b, &d, &x, &y);
        tuple<int,int,int> dxy = extendedEuclid(a,b);
        d = get<0>(dxy);
        x = get<1>(dxy);
        y = get<2>(dxy);
        if (c % d == 0 )//daca d divide pe c inseamna ca si x*c si y*c se divid prin d
            out << ( x * c/d) << " " <<  (y * c/d) << '\n';
        else
            out << "0 0\n";//altfel nu avem solutie
    }
    return 0;
}