2010/03/10
一、辗转相除法：
大数除以小数 余数1
小数除以余数1 余数2
余数1除以余数2 余数3
若余数3为0，则余数2为所求，否则一直辗转相除
二、更相减损法
大数除以小数 余数1
小数除以余数1 余数2
余数1除以余数2 余数3
若余数3为0，则余数2为所求，否则一直辗转相除
int gys(int m,int n)
{
int t,r;
if(m<n)
{t=m;m=n;n=t;}
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
return n;
}
{
int t,r;
if(m<n)
{t=m;m=n;n=t;}
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
return n;
}
二、更相减损法
int jsf(int a,int b)
{
while(a!=b)
{
if(a>b)
a-=b;
else
b-=a;
}
return b;
}
{
while(a!=b)
{
if(a>b)
a-=b;
else
b-=a;
}
return b;
}
