最大公约数（大数版）

示例：

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;
}