gcd學習

gcd函數簡介

最大公約數（greatest common divisor，gcd）:指能夠整除多個整數的最大正整數。而多個整數不能都為零。例如8和12的最大公因數為4。

求兩個整數最大公約數主要的方法：

1.窮舉法：分别列出兩整數的所有約數，并找出最大的公約數。

2.素因數分解：分别列出兩數的素因數分解式，并計算共同項的乘積。

3.短除法：兩數除以其共同素因數，直到兩數互素時，所有除數的乘積即為最大公約數。

4.輾轉相除法：兩數相除，取餘數重複進行相除，直到餘數為0時，前一個除數即為最大公約數。

gcd函數寫法

while循環（常速）

此段代碼a、b可以為0

inline int gcd(int a,int b) {
    int r;
    while(b>0) {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
           

三目運算符（較快）

此段代碼a、b可以為0

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

位運算（超快）

此段代碼a、b不能為0

inline int gcd(int a,int b) {
    while(b^=a^=b^=a%=b);
    return a;
}
           

(b=a=b=a%=b)相當于(b=(a=(b=(a%=b))))相當于a%=b,b=a,a=b,b^=a

其中b=a,a=b,b^=a相當于swap(a,b)，詳見卡常技巧第3條。

是以(b=a=b^=a%=b)等價于a%=b,swap(a,b)，這就是gcd函數的一般寫法。

if+while（較快）

此段代碼a、b可以為0

inline int gcd(int a,int b) {
	if(b) while((a%=b) && (b%=a));
	return a+b;
}
           

輾轉相除法（較快）

此段代碼a、b不能為0

inline int gcd(int a,int b) {
	if(a%b==0) return b;
		else return (gcd(b,a%b));
}
           

gcd庫函數（較慢）

此段代碼a、b可以為0

#include <algorithm>
inline int gcd(int a,int b) {
	return __gcd(a,b);
}
           

是GNU的内部函數，不是一個标準庫裡的函數，我也不太了解，平時寫題直接用這個函數挺友善的，當然也可以手寫gcd函數，它頭檔案是。