Algorithms & Data Structure : Leetcode 1979 : Find Greatest Common Divisor of Array

題目：

Find Greatest Common Divisor of Array - LeetCode

我的解法：

這題固然簡單，但我常常會忘記 GCD 該怎麼寫。。。所以將我的推導記錄下來，以增強我那少的可憐的記憶力。

一邊寫一邊感慨自己的基礎數論差的可憐，通通都忘光光了。要是數學實力還停留在高中程度的話，就方便多了。

    int gcd(int a, int b) {
        if(b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
    int findGCD(vector<int>& nums) {
        int minVal = INT_MAX;
        int maxVal = INT_MIN;
        for(int i = 0;i < nums.size();i++) {
            minVal = min(minVal, nums[i]);
            maxVal = max(maxVal, nums[i]);
            
        }
        
        return gcd(maxVal, minVal);
    }

不負責任的推導：

a : 被除數
b : 除數
p : 商
q : 餘數
a / b = p ... q ==> q = a % b
                ==> a = b * p + q
                ==> gcd(b, q) 可整除 b, q
                ==> gcd(b, q) 可整除 a
                ==> gcd(b, q) 可整除 gcd(a, b)
q = -b * p + a  ==> gcd(a, b) 可整除 a, b
                ==> gcd(a, b) 可整除 q
                ==> gcd(a, b) 可整除 gcd(b, q)
a | b ==> b / a = q ... 0
gcd(a, b) | gcd(b, q) 且 gcd(b, q) | gcd(a, b)
==> gcd(a, b) = (+-gcd(b, q))
==> 令 gcd(b, q) 為正數 
==> gcd(a, b) == gcd(b, q)
==> 因 q = a % b
==> gcd(a, b) == gcd(b, a % b)

TODO

補上空間以及時間複雜度

Reference

http://www.math.ied.edu.hk/tdg2004/Dr%20KK%20Poon/Unit_1_divisibility_admened.pdf

http://web.ntnu.edu.tw/~algo/Divisor.html
這邊有計算複雜度的方式