# GCD(UVA11417)
## [程式繳交區](https://hackmd.io/@Renektonn/S18g8y6uke/edit)
## 題目
[點我](https://onlinejudge.org/external/114/11417.pdf)

## 解題網站
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2412)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=d255)

## 演算法

1. 輸入n，若為0，則停止
2. G=0;
for(i=1;i<N;i++) {
    for(j=i+1;j<=N;j++) {
        G+=GCD(i,j);
    }
}
3. 輸出G

## 程式碼

#include <bits/stdc++.h>
using namespace std;
int gcd (int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        int g = 0;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                g += gcd(i, j);
            }
        }
        cout << g << endl;
    }

    return 0;
}

## 時間複雜度
$O(tn^2\log(n))$
$n=500, t=100$
$100\times250000\times 9=2.25\times10^8$
我覺得勉強能過

## 更好的演算法
使用動態規劃

1. 定義子問題：g(i)代表當n為i，G的值
2. 遞迴關係式：
g(n) = 1, n = 2
g(n) = g(n - 1) + gcd(j, i), j = [1, i - 1]
3. 計算順序：bottom-up，由小到大即可
4. 答案在g[n]

1. 使用動態規劃建表
2. 輸入n，若為0，則停止
3. 輸出g(n)

## 程式碼

#include <bits/stdc++.h>
using namespace std;
int gcd (int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int g[501] = {};
    g[2] = 1;
    for (int i = 3; i <= 500; i++) {
        int sum = g[i - 1];
        for (int j = 1; j < i; j++) {
            sum += gcd(j, i);
        }
        g[i] = sum;
    }
    int n;
    while (cin >> n) {
        if (n == 0) break;
        cout << g[n] << endl;
    }
    return 0;
}

## 時間複雜度
$O(max(n^2, t))$
$n=500, t=100$
計算量為$250000=2.5\times10^5$