exEuclidAlgo.cpp

template <typename T>
void exEuclidAlgo2(T a,T b,T& x,T &y) {
    T x0,y0,u0,v0;
    T x1,y1,u1,v1;
    T r0,r1,r2;
    T k;
    r0 = a;
    r1 = b;

    k = r0 / r1;
    r2 = r0 % r1;

    x0 = k;
    y0 = 1;
    u0 = 1;
    v0 = 0;

    r0 = r1;
    r1 = r2;

    //ユークリッドの互除法実行 しつつ行列Aを計算
    while(r1 != 0) {
        k = r0 / r1;
        r2 = r0 % r1;

        x1 = x0 * k + y0;
        y1 = x0;
        u1 = u0 * k + v0;
        v1 = u0;

        r0 = r1;
        r1 = r2;

        x0 = x1;
        y0 = y1;
        u0 = u1;
        v0 = v1;

    }

    //逆行列の計算
    T d = x0*v0 - y0*u0;

    x = v0/d;
    y = -y0/d;
    
}