Cod sursa(job #2386521)

Utilizator CojocariuAlexandruCojocariu Alexandru CojocariuAlexandru Data 23 martie 2019 10:42:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

struct config{
    int x, y;
};
config init1, init2, a;
int x, y, rez, cmmdc, sol1, sol2, q, i;

int euclid(int, int);
void euclidExtins(int, int, config, config);

int main(){
    fin >> q;
    for(i=1; i<=q; ++i){
        fin >> x >> y >> rez;
        if(x == 0){
            if(rez %y==0){
                fout << "0 " << rez/y << '\n';
                }
                else
                fout << "0 0\n";
            continue;
            }
        if(y==0){
            if(rez %x==0){
                fout << rez/x << " 0\n";
                }
                else
                fout << "0 0\n";
            continue;
            }
        cmmdc = euclid(x, y);
        init1.x = 1; init1.y = 0;
        init2.y = 0; init2.y = 1;
        euclidExtins(x, y, init1, init2);
        if(sol1*(rez/cmmdc) * x + sol2*(rez/cmmdc) * y == rez)
            fout << sol1*(rez/cmmdc) << ' ' << sol2*(rez/cmmdc) << '\n';
            else
            fout << "0 0\n";
        }
    return 0;
}

int euclid(int x, int y){
    if(y == 0)
        return x;
    return euclid(y, x%y);
}

void euclidExtins(int v1, int v2, config a, config b){
    int cat, rest;
    config c;
    rest = v1%v2;
    if(rest==0){
        sol1 = b.x;
        sol2 = b.y;
        return;
        }
    cat = v1/v2;
    c.x = a.x - cat*b.x;
    c.y = a.y - cat*b.y;
    euclidExtins(v2, rest, b, c);
}