#include<iostream>
using namespace std;
int GCD(int &a, int &b)
{
    int remainder;
    if (b != 0)
        while (true)
        {
            remainder = a % b;
            if (remainder == 0)
                return b;
            a = b;
            b = remainder;
        }
    else
        return a;
}
void ExtendEuclid(int a, int b,int &S,int &T)
{
    int s1 = 1, t1 = 0, s2 = 0, t2 = 1, q, r = 1, temps, tempt;;
    while (r)
    {
        q = a / b;
        temps = s1 - q * s2;
        tempt = t1-q*t2;
        s1 = s2; s2 = temps;
        t1 = t2; t2 = tempt;
        r = a % b;
        a = b;
        b = r;
    }
    S = s1;
    T = t1;
}
int main()
{
    int a, b,s,t;
    cout << "请输入要求最大公因数的两个数a, b:";
    cin >> a >> b;
    if (b > a) { int temp = a; a = b; b = temp; }
    ExtendEuclid(a, b, s, t);
    cout << endl<<s << "  " << t << endl;
    if ((s * a + t * b) == GCD(a, b))
        cout << "(s * a + t * b) == GCD(a, b),扩展的Euclid算法正确" << endl;
    else
        cout << "(s * a + t * b) != GCD(a, b)扩展的Euclid算法不正确" << endl;
}

扩展Euclid定理求s,t,并且证明定理正确。