從本文開始講將一些數(shù)論算法理論知識(shí)，以及具體題目，幫助更多學(xué)習(xí)算法的同學(xué)掌握數(shù)論算法知識(shí)。本文主要講一些數(shù)論的基礎(chǔ)和歐幾里得算法，并通過歐幾里得算法求最大公約數(shù)和最小公倍數(shù)。

一. 基礎(chǔ)知識(shí)

在開始之前，我們先來了解一些數(shù)論基礎(chǔ)知識(shí)。由于數(shù)論是研究的整數(shù)之間的規(guī)律，先來看看整除的定義

如果整數(shù)a除以非零整數(shù)b，商為整數(shù)，余數(shù)為零，我們就說a能被b整除，或者b能整除a，記作b|a，那么a叫做b的倍數(shù)，b叫做a的約數(shù)或因數(shù)。

假如整數(shù)a除以非零整數(shù)b的余數(shù)為r，那么r=a mod b，數(shù)論中用mod表示取余。

假如d是整數(shù)a和整數(shù)b的公約數(shù)，那么有d|a和d|b，即整數(shù)a和b都能被d整除，其中滿足條件最大的d叫做a和b的最大公約數(shù)，記作d=gcd(a, b)。

假如c是整數(shù)a和整數(shù)b的公倍數(shù)，那么有a|c和b|c，即整數(shù)c都能被整數(shù)a和b整除，其中滿足條件最小的c叫做a和b的最小公倍數(shù)，記作c=lcm(a, b)。

二. 歐幾里得算法

歐幾里得算法又叫做輾轉(zhuǎn)相除法，它是用來求最大公約數(shù)的，最小公倍數(shù)也可以通過它間接求出。

先來看歐幾里得算法的原理，假如a>b，且r=a mod b，那么a = k*b+r，假如d是a和b的公約數(shù)，即滿足d|a和d|b，r可以表示為r=a-k*b，因?yàn)閍和b能被d整除，那么r也能被d整除，即d|r，所以d也是b和r的公約數(shù)，那么d為最大公約數(shù)也是滿足這個(gè)條件的，所以有如下結(jié)論

上式就是一次輾轉(zhuǎn)相除了，由于余數(shù)r是逐漸減小的，到某一時(shí)刻它會(huì)為零，即

很明顯這里的m就是a和b的最大公約數(shù)了，其它公約數(shù)也一定是m的因數(shù)。我們來舉一個(gè)實(shí)例看一下這個(gè)過程，比如求21和15的最大公約數(shù)

上述就是輾轉(zhuǎn)相除的過程，具體表示為

所以最終算出21和15的最大公約數(shù)為3。以上就是歐幾里得算法的核心思想，下面代碼來實(shí)現(xiàn)一下

上面的是非遞歸方法的實(shí)現(xiàn)，其實(shí)用遞歸方法代碼更簡潔，如下

int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}

三. 求最小公倍數(shù)

最小公倍數(shù)可以通過最大公約數(shù)求得，最小公倍數(shù) = 兩數(shù)之積 / 最大公約數(shù)，這個(gè)結(jié)論我們來證明一下。

根據(jù)最大公約數(shù)的定義，d是最大的能同時(shí)整除a和b的整數(shù)，那么a=k1*d，b=k2*d，gcd(k1,k2)=1，那么公倍數(shù)滿足被a和b整除，那么公倍數(shù)必須有k1和k2的乘積，又要要求最小，那么再乘以一個(gè)d就是最小的了，即

所以在計(jì)算最小公倍數(shù)時(shí)候，通常只需要先計(jì)算出最大公約數(shù)就可以了，再通過上述公式就可以求出最小公倍數(shù)。

四. 多個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)

有時(shí)候，我們不僅求兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)，還需要求出多個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)，這個(gè)其實(shí)也不難，多個(gè)數(shù)的求法可以轉(zhuǎn)化為兩兩求然后合并即可。

例如求整數(shù)a、b、c、d的最大公約數(shù)，那么先求出a和b的最大公約數(shù)，假如為m1，接下來再求m1和c的最大公約數(shù)，假如為m2，最后再求m2和d的最大公約數(shù)m3，最終m3就是整數(shù)a、b、c、d的最大公約數(shù)。最小公倍數(shù)的方式也一樣，就不列舉了。

后面會(huì)持續(xù)更新更多數(shù)論的算法理論知識(shí)，歡迎大家多關(guān)注！