[BOJ] 9613 GCD 합 - JAVA

1. 문제

9613번: GCD 합

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  숫자를 전부 입력받은 뒤 각 쌍마다 gcd를 구해서 sum에 더하면 된다. 이 때, sum의 최대값은 1000000*100이므로 long타입이어야 한다.

2.  gcd(a,b)==gcd(b,a%b) 다. 만약 a%b가 0이라면 gcd(a,b)는 b다. 이 공식을 함수로 만들었다.

import java.io.*;
import java.util.*;

public class BOJ_9613_GCD합 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      StringTokenizer st;
      int N;
      int[] input;
      long sum;
      for(int tc=0;tc<T;tc++){
         st = new StringTokenizer(in.readLine());
         N = Integer.parseInt(st.nextToken());
         input = new int[N];
         for(int i=0;i<N;i++){
            input[i] = Integer.parseInt(st.nextToken());
         }
         sum = 0;
         for(int i=0;i<N-1;i++){
            for(int j=i+1;j<N;j++){
               sum += gcd(input[i], input[j]);
            }
         }
         sb.append(sum).append('\n');
      }
      System.out.print(sb);
   }
   private static int gcd(int a, int b){
      if(a%b==0) return b;
      return gcd(b,a%b);
   }
}

---

3. 결과

sum 타입때문에 한 번 틀렸다.