[Algorithm] 확장 유클리드 알고리즘 Extended Euclid Algorithm

http://codepractice.tistory.com/79

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
 
using namespace std;
 
int RecursiveEuclid(int a, int b)
{
    if (a < b)
        swap(a, b);
 
    if (a%b == 0)
        return b;
    else
        return RecursiveEuclid(b, a%b);
}
 
template<typename T>
T LoopEuclid(T a, T b)
{
    if (a < b)
        swap(a, b);
 
    while (a%b != 0)
    {
        T tmp = a;
        a = b;
        b = tmp%b;
    }
    return b;
}
 
 
template<typename T>
pair<T, T> ExtendedEuclid(T a, T b)
{
    T q = (a / b);
    T r = a%b;
    T s1, s2, t1, t2;
    s1 = 0;
    t1 = 1;
    s2 = 1;
    t2 = 0;
 
 
    while (r!=0)
    {
        T temps = s2;
        s2 = s1;
        s1 = temps - s1*q;
 
        T tempt = t2;
        t2 = t1;
        t1 = tempt - t1*q;
        
        a = b;
        b = r;
        q = (a / b);
        r = a%b;
    }
    return pair<T, T>(s1, t1);
}
 
 
 
int main()
{
    int a = 69;
    int b = 23;
    pair<int, int> sol = ExtendedEuclid(a,b);
    cout << sol.first << "*" << a << "+" << b << "*" << sol.second << "=" << LoopEuclid(a, b) << endl;
    a = 67;
    b = 23;
    sol = ExtendedEuclid(a, b);
    cout << sol.first << "*" << a << "+" << b << "*" << sol.second << "=" << LoopEuclid(a, b) << endl;
}