Cod sursa(job #2722561)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 12 martie 2021 23:27:06
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>

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

int euclid (int a, int b, int&x, int &y) {
    if (b==0) {
        ///a*x+b*y=d
        ///a*x=d
        ///x=d/a
        ///x=a/a
        ///x=1, y=orice
        x=1,y=0;
        return a;
    }
    else {
        int xa,ya;
        int d=euclid(b,a%b,xa,ya);
        ///b*xa+(a%b)*ya=d
        ///a%b=a/b*c
        ///b*xa+(a-b*c)*ya=d
        ///a*x+b*y=d
        ///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(ya-x)=0
        ///ya-x=0 =>x=ya
        ///xa-c*ya-y=0 =>y=xa-c*ya
        int c=a/b;
        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;
        ///a*x+b*y=c
        int d=euclid(a,b,x,y);
        if (c%d==0) {
            fout<<x*c/d<<" "<<y*c/d<<"\n";
        }
        else {
            fout<<"0 0\n";
        }
    }
    return 0;
}