Cod sursa(job #2722562)

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

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

long long euclid (long long a, long long b, long long&x, long long &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 {
        long long xa,ya;
        long long 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
        long long 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
        long long 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;
}