Cod sursa(job #3293306)

Utilizator EricRaiaEricRaia EricRaia Data 11 aprilie 2025 14:04:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstdlib>
using namespace std;

ifstream in; ofstream out;
long a,b,d,c[61],x,y,cm,T; short k;

void cmmdc (long u, long v, long& w) {
     long z;
     k=0;
     while (v) {
         k+=1;
         c[k]=u/v;
         z=u; u=v; v=z%v;
     }
     w=u;
}

int main () {
    in.open ("euclid3.in"); out.open ("euclid3.out");
    short i; long j;
    in>>T;
    for (i=1; i<=T; i++) {
        in>>a>>b>>d;
        if (d<0) {a*=-1; b*=-1; d*=-1; }
        if (!a)
           if (b) {
              x=0;
              if (!(d%b)) y=d/b; else y=0;
           }
           else {
                x=0; y=0;
           }
        else
            if (!b) {
               y=0;
               if (!(d%a)) x=d/a; else x=0;
            }
            else {
                 cmmdc (abs (a),abs (b),cm);
                 if (!(d%cm)) {
                    x=0; y=1;
                    for (k-=1; k>=1; k--) {
                        j=x; x=y; y=j-y*c[k];
                    }
                    x*=(d/cm); y*=(d/cm);
                    if (a<0) x*=-1; if (b<0) y*=-1;
                 }
                 else {
                      x=0; y=0;
                 }
            }
        out<<x<<" "<<y<<"\n";
    }
    in.close (); out.close ();
    return 0;
}