#include <iostream>
#include <cstdio>
using namespace std;
void extendedGcd(int x, int y){
int q, r, r1, r2, s, s1, s2, t, t1, t2;
s1 = 1;
s2 = 0;
t1 = 0;
t2 = 1;
r1 = x;
r2 = y;
while(r2!=0){
q = r1 / r2;
r = r1 % r2;
s = s1 - q*s2;
t = t1 - q*t2;
r1 = r2;
r2 = r;
s1 = s2;
s2 = s;
t1 = t2;
t2 = t;
}
printf("%d %d %d\n", r1, s1, t1);
}
int main(){
int x,y;
while(cin>>x>>y){
extendedGcd(x, y);
}
return 0;
}
Tuesday, July 16, 2013
How to find Extended GCD using C++
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment