原理:(a,b)的公因数等价(b,amodb);
简单证明: amodb=a-[a/b]b;
=a-cb(c为常数)
–>即证明(a,b)=(b,a-cb);
先左边: 有公因数d满足：d|a&&d|b –>(d|a,d|b)–>d|ax+by—>d|a-cd,x=1,y=-c;
再右边: d|b&&d|a-cb–>d|(a-cb)+c*b—>d|a&&d|b

C++

#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main(void)
{
    int k;cin>>k;
    while(k--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
return 0;    
}