最大公约数

发表于   |   分类于   |     |   阅读次数

这几天做了计蒜客编程比赛，被一道题目卡了很久，辗转很久，找管理看了源码后，感悟非ACM选手，写算法题真的是会丧智啊！！
不过呢，积累点知识也是不错的，毕竟再过几个月还要参加校招，肯定回有所帮助的。ps,刷题真的超级费时间哦~~

今天，写点关于最大公约数的知识点，这个是很常见的文题了，一般的算法题绝对不会赤裸裸的考你最大公约数，不过有些题目是会用到的。

说到最大公约数，不知道欧几里得算法，想必也有耳闻吧。哈哈，博主其实就是后者啦。数学渣~~~
简单来说下这个定理。
先给出结论：gcd(a,b) = gcd(b,a mod b); gcd表示求最大公约数。
证明：任意的数a可以写成 a = kb + r,其中k = a/b,r = a%b
那么，r = a - kb.
假设，d是a,b的最大公约数。即d也是r的公约数
所以，gcd(a,b) = gcd(b,r);

代码：

1
2
3
4
int gcd(int a, int b)
{
	return b==0 ? a ? gcd(b,a%b); 
}