(4) 最大公约数
(greast common divisor简称“gcd”)
递归版辗转相除法(欧几里得算法):核心是gcd(a , b) = gcd(b , a % b)
原理:
由基本定理得:当d能分别整除a,b时,d就能整除xa+yb。
显然a % b = a - c * b(其中c=a/b)。
即证:(a , b) = (b , a - c * b)
记d=(a,b),则d|a,d|b,所以根据基本定理得d|a-cb,所以d=gcd(b , a-cb)
记d=(b , a-cb) , 则d|b , d|a-cb ,所以根据基本定理得:d|(cb)+(a-cb) 即a|b ,所以d=(a , b)
所以(a , b) = (b , a-c*b)成立,说明(a,b)的公约数就是(b , a - c * b)的公约数,所以等号两边的最大公约数相同。
不断地辗转相除直到第二个参数为0,因为0模上任何一个非零的整数都是0,所以任何一个数都可以看作是0的约数,而b的最大约数是b,那取交集后,gcd(b,0)当然是b。
所以gcd(a , b) = gcd(b , a % b)成立
//核心代码,非常非常简单
int gcd(int a , int b)
{
return b ? gcd(b , a % b) : a;
}