示例：
99999999999999999999（20位） 与 6666666666666666666（20位）: gcd= 33333333333333333333（20位）
思路：全部写在注释里面了~
/***********************************************************
FileName: 大数最大公约数（位移版）.cpp
Author: Dojking
Version : V1.0
Date:2014/3/16
Function List:
1.int main() 主函数
2.void strmod(); 模拟大数取余
3.void strsub(); 模拟大数减法
History:
<author> <time> <version > <desc>
Dojking 2014/3/16 1.0 build
***********************************************************/
#include <iostream>
#include <string>
using namespace std;
int pos, zero, len1, len2;/*pos:匹配位置，zero:str1高位最后一个0的位置，len1:str1长度，len2：str2长度*/
string str1, str2, mod; /*str1：大数1，str2：大数2，mod：每步的余数*/
/********************************************************************************************************
strsub()函数：
模拟大数快速减法，末尾补0法虽然能快速的做减法，然后由于是字符串操作，末尾减0的操作实际上是无用的操作。
这里引入位移法，进行快速减法。
具体思想：（假设str1 > str2）我们先比较str1[0],str2[0]值得大小，用以确定str2与str1的匹配位置。
比如：str1=12345678 , str2=431，由于str1[0] < str2[0]，所以应当这样匹配做减法：
str1: 12345678
str2: 431
又如：str1=5173 , str2=29，由于str1[0] > str2[0]，所以应当这样匹配做减法：
str1: 5173
str2: 29
同时，直接在str1里面保存减好的值。并且用str2的长度控制减法的次数。
********************************************************************************************************/
void strsub() /*该函数用大数减法，模拟取余*/
{
int i,j;
pos = zero+1; /*pos指向str1有效位的第一位*/
if (str1[pos] < str2[0])/*如果str1[pos] < str2[0]，说明不能从最高位开始减。如123 - 45也不能从最高位开始减*/
{
++pos; /*后移一位*/
}
for (i=pos+len2-1,j=len2-1; j >= 0; --i,--j) /*模拟减法*/
{
if (str1[i] < str2[j] || str1[i] == 'f') /*需要借位，f表示-1*/
{
if (str1[i-1] != '0') /*高位不为0*/
{
str1[i-1] -= 1; /*向高位借位*/
}
else /*高位为0，借位后变为-1，用f表示-1*/
{
str1[i-1] = 'f'; /* f = -1 */
}
if (str1[i] == 'f') /*本位为f，直接用-1代替*/
str1[i] = ((-1+10)-(str2[j]-'0')+'0');
else /*本位不为f，执行 '-' 操作*/
str1[i] = ((str1[i]-'0')+10-(str2[j]-'0')+'0');
}
else /*不需要借位，直接 '-' 操作*/
{
str1[i] = ((str1[i]-'0')-(str2[j]-'0')+'0');
}
}
while (str1[zero+1] == '0' && (len1-zero) != 2) /*去掉相减后高位上的无效0。(len1-zero) != 2:防止全为0的情况)*/
{
++zero;
}
}
/****************************************************************************
strmod()函数：
主要负责一些值的初始化，舍去str1高位上的无效0，和当str1 < str2时跳出循环。
****************************************************************************/
void strmod() /*此函数作用相当于 str1 %= str2，注意str1,str2都是全局变量*/
{
zero = -1; /*zero指向当前高位上最后一个0的位置*/
len1 = str1.size(); /*获得串长度*/
len2 = str2.size();
/*如果str1 < str2，则跳出。注意字符串模拟数字大小比较，同时str1前面可能有多余的0*/
while (! (len1 - (zero+1) < len2 || str1[zero+1] < str2[0] && (len1 - (zero + 1) <= len2)) )
{
strsub(); /*进行大数减法，模拟取余*/
}
mod = ""; /*重置mod，避免对下面的mod+=造成影响*/
while (zero < len1-1) /*舍去str1高位上的0，将有效数字拷贝进mod，传进main函数，进行下次辗转*/
{
mod += str1[++zero];
}
}
/****************************************************************************************
main()函数：
主函数，函数中省去了，swap()函数，因为不管是str1>str2，还是str1<str2都不影响执行结果。
分析：如果str1 < str2。程序执行到strmod()中将不进入while(1)，然后返回main()函数。
在main()-while()中交换了str1,str2的值。
同时，主函数中增加了一个循环函数，便于测试多组数据，而不是运行一次只能测试一组数据。
****************************************************************************************/
int main()
{
while (1) /*便于测试多组数据*/
{
cin>>str1>>str2; /*输入两个大数*/
if (str1[0] == '0' || str2[0] == '0') /*请不要输入0*/
{
cout<<"input error"<<endl;
break;
}
while (str2[0] != '0') /*大数取余运算跳出条件*/
{
strmod(); /*此函数作用相当于 str1 %= str2，注意str1,str2都是全局变量*/
str1 = str2; /*str1保存较大数*/
str2 = mod; /*str2保存余数*/
}
cout<<str1<<endl; /*输出求余结果*/
}
return 0;
}