if(n == 0) return m;
else return Gcd(n,m%n); }
int main(void ) {
int m,n;
printf(\scanf(\
printf(\return 0; }
程序： INPUT m,n DO
r=mMODn m=n n=r
LOOP UNTIL r=0 PRINT m END
pascal实现
function gcd(a,b:integer):integer; begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b); end ;
数据举例
其中“a mod b”是指取 a ÷ b 的余数。
例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出： a b a mod b
123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12
462 12 6 12 6 0 时间复杂度
辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。 编辑本段辗转相除法求不定方程的特解
辗转相除法可以求出不定方程的一组整数解。
设不定方程为a x+b y=c，其中a,b,c为整数且lcm(a,b)|c
a,b辗转相除的算式为 b=q(1) a+r(2) a=q(2) r(2)+r(3) r(2)=q(3) r(3)+r(4) ...
r(n-2)=q(n-1)r(n-1)+r(n) r(n-1)=q(n)r(n)
其中r(n)为lcm(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0 第i个算式为
r(i-1)=q(i)r(i)+r(i+1)
所以r(i+1)=r(i-1)-q(i)(ri) (*)
用公式(*)可以得到r(n)=lcm(a,b)关于a,b的线性组合sa+tb=lcm(a,b)
所以不定方程a x+b y=c的一组特解为 x=sc/lcm(a,b) y=tc/lcm(a,b) 例如：
不定方程为326x+78y=4 求(163,39)的算式为
326=4*78+14 14=326-4*78
78=5*14+8 8=78-5*14 14=1*8+6 6=14-1*8 8=1*6+2 2=8-1*6 6=3*2 所以 2
=8-6=8-(14-8)
=2*8-14=2*(78-5*14)-14
=2*78-11*14=2*78-11*(326-4*78)
=46*78-11*326
即2=(-11)*326+46*78 所以4=(-22)*326+72*78
所以x=-22,y=72是不定方程326x+78y=4的一组特解 注：q(i)，r(i)，括号中的是下标，lcm是求最小公倍数
