Tuesday, July 16, 2013

How to find Extended GCD using C++

#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;
}

No comments:

Post a Comment