D. GCD

• 本題源自於Online Judge(UVa)：11417 - GCD

STL "__gcd" function

C++ 14的<algorithm>有內建一個__gcd的函數，不過實在很不顯眼。
(註：是兩個底線)

# include <iostream>
# include <algorithm>

int main(){
    int G,N,i,j;
    
    while(std::cin>>N && N != 0){
        G = 0;
        for(i = 1 ; i<N ; i++)
            for(j = i+1 ; j<=N ; j++)
                G += __gcd(i,j);

        std::cout << G << '\n';
    }
}

---

More about GCD

以下提供幾個以輾轉相除法(Euclidean algorithm)實作GCD的方式作為參考。

輾轉相除法(Euclidean algorithm) - Recursion version :

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

輾轉相除法(Euclidean algorithm) - Loop version :

int gcd(int a,int b){
    int c;
    while(b != 0){
        c = a%b;
        a = b;
        b = c;
    }
    
    return a;
}

輾轉相除法(Euclidean algorithm) by wiki :

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