Cod sursa(job #2710746)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 22 februarie 2021 23:01:41
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>

using namespace std;
int a,b,c,d,q,x,y;

int cmmdc(int a, int b,int &x, int &y) {
    if  (b==0) {///ax+by=d
                ///ax=d
                ///x=d/a
                ///y=oricat
        x=1;
        y=0;
        return a;
    }
    else {
        int d=cmmdc(b,a%b,x,y);
        int xa=x;
        int ya=y;
        int c=a/b;
        ///b*xa+(a%b)*ya=d
        ///inlocuim a%b cu a-b*c, unde c este catul impartirii a/b
        ///b*xa+(a-b*c)ya=d
        ///a*x+b*y=d ///vrem sa aflam x si y
        ///=> b*xa+(a-b*c)ya=a*x+b*y
        ///=> b*xa+a*ya-b*c*ya=a*x+b*y
        ///=> b(xa-c*ya-y)=a(x-ya)
        ///Una dintre solutii este
        /// xa-c*ya-y=0 De unde rezulta y=xa-c*ya
        /// x-ya=0 De unde rezulta x=ya
        x=ya;
        y=xa-c*ya;
        return d;
    }
}

int main() {
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    for (fin>>q;q--;) {
        fin>>a>>b>>c;
        d=cmmdc(a,b,x,y);
        if (c%d==0) fout<<x*(c/d)<<" "<<y*(c/d)<<"\n";
        else fout<<"0 0\n";
       /// fout<<a<<" "<<"*"<<" "<<x<<" "<<"+"<<" "<<b<<" "<<"*"<<" "<<y<<" "<<"="<<" "<<d<<"\n";
    }
    return 0;
}