[백준 9613번] GCD 합

 

www.acmicpc.net/problem/9613

9613번: GCD 합

 

[문제]

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

 

<알고리즘 분류> 수학, 기초수학, 정수론, 유클리드 호제법

 

[input]

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

[output]

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

---

 

 

---

 

[풀이 방법]

1. BufferedReader와 BufferedWriter 사용

2. 테스트 개수를 입력받아 변수 t에 저장

3. t개만큼 입력받아 변수 S에 저장한 후 공백으로 구분하여 배열 s에 저장

4. 입력받을 수의 개수를 입력받아 변수 n으로 저장

5. 나머지 입력받은 수는 test 배열에 정수로 변환하여 저장

6. 미리 정의한 최대공약수를 구하는 함수 gcd를 활용하여 각 케이스의 최대공약수를 구해 변수 gcdSum에 저장

7. 각 테스트 케이스의 최대 공약수의 합을 배열 GCDs에 저장

8. 배열 GCDs에 저장된 값을 한 줄씩 출력

 

---

 

성공 코드