Cod sursa(job #3293306)
Utilizator | 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;
}