---
title: 1D GCD
tags: solution
---

# D. GCD

- 本題源自於Online Judge(UVa)：[11417 - GCD](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2412)

## 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)](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)實作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;
}