//求整數a、b的最大公約數

#include

//用歐幾里得算法求最大公約數d
int?gcd（int?dint?e）
{
	
	int?c;
	
	if（d	{
		c=d;
		d=e;
		e=c;?
	}
????
	while（e）
	{
		c=d%e;
		d=e;
		e=c;
	}
????return?d;
}

int?Extended（int?aint?b）
{
	int?x1x2x3y1y2y3t1t2t3q;
	x1=1;x2=0;x3=b;
	y1=0;y2=1;y3=a;
	
	while（（y3!=1）&&（y3!=0））
	{

			q=x3/y3;
			t1=x1-q*y1;
			t2=x2-q*y2;