gcd.cpp

求sa和tb的和使等于a和b的最大公约数

#include<iostream.h>
double f(double a,double b)
{ //int r,q,k,n,m,temp;
	//cout<<"请输入两个正整数"<<endl;
	//cin>>n;
  //q=n;
	//cin>>m;
	//k=m;
	double m,n,temp;
	n=a;m=b;
	int r;
	if(n<m)
	{
		temp=n;
		n=m;
		m=temp;
	}
	while(r!=0)
	{ 
		r=(int)n%(int)m;
		n=m;
		m=r;
	}
	//cout<<q<<"和"<<k<<"的最大公约数是"<<n<<endl;
	return n;
}
void main()
{
	double a,A,b,B,te,TE;
	int j=1,i,r,rr;
	int biaozhi;
	cout<<"下面的程序求(a,b)=sa+tb"<<endl;
	cout<<"请输入a和b"<<endl;
	cout<<"a=";
	cin>>a;
	A=a;
    cout<<"b=";
	cin>>b;
	B=b;
	if(a<b)
	{
		te=a;
		a=b;
		b=te;
		TE=A;
		A=B;
		B=TE;

	}
	int aa[100];
	while(r!=0)
	{   rr=(int)a/(int)b;
	    aa[j]=rr;
		r=(int)a%(int)b;
		a=b;
		b=r;
		j++;
	}
	/*for(i=1;i<=j-1;i++)
		cout<<aa[i]<<endl;*/
	int s[100],t[100];
	s[0]=1;
	s[1]=0;
	t[0]=0;
	t[1]=1;
	for(i=2;i<=j-1;i++)
	{
		s[i]=s[i-2]-aa[i-1]*s[i-1];
		t[i]=t[i-2]-aa[i-1]*t[i-1];
	}
	cout<<"s="<<s[j-1]<<"   "<<"t="<<t[j-1]<<endl;
	/*for(i=2;i<=j-1;i++)
		cout<<s[i]<<" "<<"  "<<t[i]<<endl;*/
	biaozhi=(int)f(A,B);
	cout<<A<<"和"<<B<<"的最大公约数是"<<biaozhi<<"="<<"("<<A<<","<<B<<")"<<"="<<s[j-1]<<"*"<<A<<"+"<<t[j-1]<<"*"<<B<<endl;
    
	if(biaozhi==1&&t[j-1]>0)
		cout<<B<<"的逆元是"<<t[j-1]<<endl;
	if(biaozhi==1&&t[j-1]<0)
        cout<<B<<"的逆元是"<<A+t[j-1]<<endl;
}