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

一. 基礎(chǔ)知識

在開始之前，我們先來了解一些數(shù)論基礎(chǔ)知識。由于數(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，因為a和b能被d整除，那么r也能被d整除，即d|r，所以d也是b和r的公約數(shù)，那么d為最大公約數(shù)也是滿足這個條件的，所以有如下結(jié)論

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

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

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

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

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

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

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

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

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

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

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

有時候，我們不僅求兩個數(shù)的最大公約數(shù)和最小公倍數(shù)，還需要求出多個數(shù)的最大公約數(shù)和最小公倍數(shù)，這個其實也不難，多個數(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ù)的方式也一樣，就不列舉了。

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