Day 0x7 UVa11417 GCD

Virtual Judge
ZeroJudge
- Zerojudge 直接破图

题意

输入一数字 N，根据定义输出结果 G

需要注意的点有：

重复输入
读到 0 就结束程序

G 的定义

题目都直接给 code 了，就拿来抄参考吧

G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=GCD(i,j);
}
/*Here GCD() is a function that finds
the greatest common divisor of the two
input numbers*/

解法

抄参考之前，一样先把重复输入架构写好

int N;

while(scanf("%d", &N)){
    if(N == 0){
        break;
    }
    else{
        ...
    }
}

开始抄参考，因为根据定义 G 是用 Σ 叠加，所以每笔测资都要记得先初始化 G = 0

else{

    G = 0;

    for(i = 1; i < N; i++){
        for(j = i + 1; j <= N; j++){
            G = G + GCD(i, j);
        }
    }

    printf("%d\n", G);
}

本题最精华之部分 - 最大公因数，这边使用递回的辗转相除法版本，至於什麽是辗转相除法，我们一样交给专业的来解释
- YouTube - 辗转相除法
- Wiki - 辗转相除法的计算机实现
```
int GCD(int a, int b){
    if(b == 0){
        return a;
    }
    else{
        GCD(b, a % b);
    }
}
```

用三元运算子可以写成邪教般的一行版

int GCD(int a, int b){
    return b == 0 ? a : GCD(b, a % b);
}

C code

#include<stdio.h>

int GCD(int a, int b){
    return b == 0 ? a : GCD(b, a % b);
}

int main(){

    int G;
    int N;
    int i, j;

    while(scanf("%d", &N)){
        if(N == 0){
            break;
        }
        else{

            G = 0;

            for(i = 1; i < N; i++){
                for(j = i + 1; j <= N; j++){
                    G = G + GCD(i, j);
                }
            }

            printf("%d\n", G);
        }
    }

    return 0;
}

讨论

最後分享一下，假如各位在练习这题，可能会查其他写法，刚刚碰巧看到这篇 Misster Hao's Blog - 【CPE】UVA 11417 GCD 一颗星 by C++，里面有提到：

比较要注意的是我有多加一个判断是当 a ==0 时也回传0
但是我记得n和0的GCD就是n呀(?)
我加上这个判断才AC(???)
挖马母灾数学上 0 和 N 的最大公因数应该要是多少，但是这题因为 G 的定义写得很清楚，从 i = 1 开始，所以如果写成 i = 0 开始，这圈 G 的值都不能更新，而且会导致内层多跑 N 圈
这位作者可能不像我抄参考题目的 code，是自己手打，所以没注意到这点，不过能发现问题出在哪，然後尝试找出解决办法我觉得很厉害