淺談如何計算 $gcd$ 與 $a ^ b$
======
> author: jeeeerrrpop

# 最大公因數
首先最直接的做法就是枚舉所有可能的因數如下：

int gcd(int a, int b){
    for(int i = min(a, b); i >= 2; i--){
        if(a % i == 0 && b % i == 0)return i;
    }
    return 1;
}

但是我們想要更快的求出兩個數字的最大公因數！
這個時候我們想到一個東西叫做[輾轉相除法](https://zh.wikipedia.org/zh-hant/輾轉相除法)。
> 輾轉相除法基於如下原理：兩個整數的最大公因數等於其中較小的數和兩數的差的最大公因數。[name=輾轉相除法的維基百科]

所以根據上述的內容我們可以改成這樣寫：

int gcd(int a, int b){
    if(a > b)swap(a, b);
    if(b % a == 0)return a;
    return gcd(a, b-a);
}

哇用到了上課教的遞迴感覺就很厲害，這樣應該就可以執行很快了，但是真的有比迴圈快嗎？
答案是其實這樣沒有快多少～

gcd(2, 100043 * 2 + 1)
//100043是質數

如果你要計算以上的gcd你會發現gcd這個函式會被你呼叫高達量級10^5左右，那如果我把100043換成量級為1000000007(這個也是質數)，那你肯定一秒內跑不完。
所以我們該怎麼優化呢？

你會發現對於以上的測資，呼叫gcd()的a其實一直都沒變，反倒是b每次減2，會減到b小於a為止。
一直減一直減一直減，是不是就會想到除法！
所以上述的事情其實等價於直接取除a之後的餘數是多少就好！
所以我們可以統整出以下的code，比上述所有的Code都短，但是能在數值取log次數內找到gcd喔～

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

:::info
當然你也可以直接想出最後這個寫法，只是我個人認為這樣一路推到最後這種做法，滿好理解的。
至於為什麼輾轉相除法一定能找到gcd()，可以參考維基百科的證明～
:::

# 冪運算
首先最直接的做法就是一路乘到b：

int power(int a, int b){
    int res = 1;
    for(int i = 0; i < b; i++){
        res *= a;
    }
    return res;
}

但是我們不能安逸於現況！
直接用迴圈一直乘看起來就很沒效率！
所以我們會想到一個很簡單的性質：
如果 b 是奇數： $a ^ {b-1} \times a = a ^ b$
如果 b 是偶數：$(a ^ {\frac{b}{2}})^2 = a ^ b$
因此我們能寫出以下的遞迴法：

int power(int a, int b){
    if(b == 0)return 1;
    if(b & 1) return a * power(a, b-1);
    return power(a, b/2) * power(a, b/2);
}

這是一個大家知道以上性質後可能會寫出來的Code，但是其實這樣的時間複雜度和用迴圈寫是一樣的！
每次 b會除以2 不然就是 -1 ，應該是 log次才對啊，為什麼複雜度是O(N)？

如果你把Code改成像這樣就會從 N 變成log 了！

int power(int a, int b){
    if(b == 0)return 1;
    if(b & 1) return a * power(a, b-1);
    int tmp = power(a, b/2);
    return tmp * tmp;
}

int power(int a, int b){
    return (b == 0 ?　1 : power(a * a, b/2) * (b & 1 ? a : 1));
}

至於為什麼就留給讀者自己思考。
我們通常稱這個算法叫做快速冪。
以下提供一個同樣概念但是是以非遞迴方式實作的。
遞迴的常數通常較大，因此我習慣用以下的寫法。

int power(int a, int b){
    int res = 1;
    while(b){
        if(b & 1)res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

:::warning
power()其實很容易就overflow，因此一般我們要判斷計算的值是不是對的，會將他MOD一個大質數，例如1000000007。
:::