Cod sursa(job #2612302)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 8 mai 2020 19:45:40
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
using namespace std;
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
///ax +  by = d
///Ecuatia are solutii daca d este multiplu de cmmmdc(a,b)
///timp de executie --- complexitate log(max(a,b))
/*
a,b-coeficienti
ax +  by = d
x = y0;
y = x0 - (a/b) * y0;
========
bx0 + (a%b)y0 = d -> x ,y

=======
(a%b)xa + ((a%b) % b) *yb = d -> x0,yo

=====
(a%b)% b * x2 + (a%b)%((a%b)%b)*y2 = d => x2 =
=====
x = 1
y = 0
*/
int cmmdc_ext(int a,int b,int &x,int &y){
    if(b==0)   {
        x = 1; 
        y = 0;
        return a;
    }
    int x0,y0,d;
   d = cmmdc_ext(b,a%b,x0,y0);
    x  =y0;
    y = x0-(a/b)*y0;
    return d;
}

///a *x + b*y = d | *(c/d)


int main()
{
    int a, b,c,x,y,n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
    cin>>a>>b >> c;
    int d = cmmdc_ext(a,b,x,y);

    if(c % d == 0) {
        cout << x * (c/d) << " " << y * (c/d) << "\n";///inmultesc
    }
    else
        cout << 0 << " " << 0 << "\n";
    }
    return 0;
}