• Virtual Judge
• ZeroJudge
  • Zerojudge 直接破圖

題意

• 輸入一數字 N，根據定義輸出結果 G
• 需要注意的點有：
  1. 重複輸入
  2. 讀到 0 就結束程式
  3. 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，是自己手打，所以沒注意到這點，不過能發現問題出在哪，然後嘗試找出解決辦法我覺得很厲害