最大公约数

xiaoxiao2021-02-28  17

最大公约数

利用辗转相除法计算a和b最大公约数(greatest common divisor),该方法基于以下定理:

g c d ( a , b ) = g c d ( b , a % b ) gcd(a, b) = gcd(b, a \% b) gcd(a,b)=gcd(b,a%b)

证明:

设 a = kb + r,则有 r = a - kb。设d是a和b的一个公约数,则d也必是r的一个约数。r = a % b,所以d是b和 a % b 的一个公约数。由b的任意性,可得a和b的公约数都是b和 a % b 的公约数。又 a = kb + r,所以b和 a % b 的公约数都是a和b的公约数。所以 gcd(a, b) = gcd(b, a % b)。证毕。

同时,0和任意一个整数a的最大公约数都是a。

int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
转载请注明原文地址: https://www.6miu.com/read-2650270.html

最新回复(0)