Divisor - 演算法筆記

以數學符號來表示，擴展輾轉相除法可以找出a b 兩數的最大公因數d ，還可以順便找出滿足ai + bj = d 的兩個整數倍率i j ，並且讓|i| 與|j| 最小。

遞推法。

複製a b 成為u v ... Divisor 使用乘法，湊得給定數字。

給你一個數，例如12。

哪些數字相乘，可以得到12呢？ 例如1×12=12、2×6=12、3×4=12。

使用乘法，分解給定數字。

湊合與分解，一體兩面。

12可以分解成哪些數字相乘呢？ 例如12=1×12、12=2×6、12=3×4。

一個數字分解成的數字叫做「因數」。

DivisorGeneration:TrialDivisionAlgorithm DivisorGeneration 「因數生成」。

一個數字的所有因數，通通列出來。

0:012...5:1510:12510 1:16:123611:111 2:127:1712:1234612 3:138:124813:113 4:1249:13914:12714 一個數字的所有因數 「試除法」。

嘗試每個數字作為因數。

時間複雜度O(n)。

voiddivisor_generation(intn) { for(intd=1;d<=n;d++) if(n%d==0) cout<b)swap(a,b); if(a==0)return0; intmaxd=1; for(intd=2;d*d<=a;++d) if(a%d==0) { //d是a的因數 if(b%d==0) maxd=max(maxd,d); //a/d是a的因數 if(b%(a/d)==0) maxd=max(maxd,a/d); } returnmaxd; } GreatestCommonDivisor:EuclideanAlgorithm EuclideanAlgorithm（Euclid'sAlgorithm） 幾何學之父歐幾里德所發明的「輾轉相除法」，用來求兩數的最大公因數。

幾何學之父原來跟數論也扯得上關係。

由於兩數必定是由最大公因數的整數倍所組合而成，故其差值也必定由最大公因數的整數倍所組合而成，不管兩數如何輾轉相減、輾轉求餘數，其得到的值都會是最大公因數的倍數。

把最大公因數想成是疊積木就簡單多了。

求出了差值後，原問題便縮小成了跟原問題類似的問題。

也就是說，輾轉相除法採取了Divide-and-ConquerMethod。

時間複雜度O(log(min(a,b)))，其中整數運算預設為O(1)。

原理是FibonacciSequence，詳情請見離散數學教科書。

迴圈版本。

//令a大b小，比較容易思考。

intgcd(inta,intb) { //大小不對，交換位置。

if(a>1,b>>1)<<1; elseif((a&1)==0) returngcd(a>>1,b); elseif((b&1)==0) returngcd(a,b>>1); else returngcd(min(a,b),abs(a-b)); } intgcd(inta,intb) { intc=0; //記錄gcd乘二乘了幾次 while(a&&b) //如果ab都是正數 //如果ab都是偶數：a/=2,b/=2,gcd乘二 if(!(a&1)&&!(b&1)) a>>=1,b>>=1,c++; //如果a是偶數、b是奇數：a/=2 elseif(!(a&1)) a>>=1; //如果a是奇數、b是偶數：b/=2 elseif(!(b&1)) b>>=1; //如果ab都是奇數：判斷ab大小，求出餘數。

elseif(a>b) a-=b; else b-=a; //不為零的數，乘上c個2，就是gcd。

returnmax(a,b)<>=1,b>>=1,c++; while(a) if (!(a&1))a>>=1; elseif(!(b&1))b>>=1; else { intr=abs(a-b)>>1; if(a