UVa -- GCD 之夜

UVa 題庫：

GCD and/or LCM (6/11)
106 - Fermat vs. Pythagoras	discuss	Lev 2	--- ? ---
332 - Rational Numbers from Repeating Fractions	discuss	Lev 3	--- ? ---
408 - Uniform Generator	discuss	Lev 2	✔ 0.015s/1683
412 - Pi	discuss	Lev 2	--- ? ---
10407 - Simple division	★ discuss	Lev 3	✔ 0.022s/1035
10892 - LCM Cardinality	★ discuss	Lev 4	--- ? ---
11388 - GCD LCM	discuss	Lev 3	✔ 0.015s/1838
11417 - GCD	discuss	Lev 2	✔ 0.332s/2409(1)
11774 - Doom's Day	discuss	Lev 5	--- ? ---
11827 - Maximum GCD	★ discuss	Lev 3	✔ 0.022s/1029
12068 - Harmonic Mean	discuss	Lev 5	✔ 0.025s/283(2)

照著練習就可以了

好用的演算法就是輾轉相除法

// Euclidean Algorithm
long long gcd(long long a, long long b)
{ 

        while (b)
        {
                long long t = b; 

                b = a % t; 

                a = t; 

        }
        return a;
}



理論上能用 non-recursive 版本的計算方式就用 non-recursive，比較快。

原則上沒太大問題，有問題的就先跳過，改天有時間再慢慢做。