辗转相除法 - 图文

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是求最小公倍数