pascal求两个数（位数≤2000）的最大公约数，用Gcd且要高精度，求程序

题目：
最大公约数gcd
问题描述
对于两个整数A和B，如果整数D同时整除A和B，则称D为A和B的公约数，称这样的D中最大的公约数为最大公约数，记为G或GCD(A,B)。这个问题要求你求出两个整数的最大公约数。
输入描述
第一行一个整数表示A；
第二行一个整数表示B。
输出描述
一行一个整数表示G。
输入样例
10000000000000000000000000000000000000000
10000
输出样例
10000
输入样例
60
22
输出样例
2
数据约定
保证A和B都为正整数。
对于30%的数据，保证A和B都在10^18范围以内；
对于50%的数据，保证A和B至多不超过100位；
对于100%的数据，保证A和B至多不超过2000位。

好像是哪个省的省选原题

gcd(2a,2b)=gcd(a,b)*2
gcd(2a,b)=gcd(a,b)
gcd(a,b)=gcd(a,b-a)