[문제] 백준 9613번 GCD합

www.acmicpc.net/problem/9613

9613번: GCD 합

 

풀이

 

숫자 하나는 1,000,000을 넘지 않으니 int형으로 선언해도 된다.

하지만 GCD의 합은 int형의 범위를 넘어설 수 있으니 long형으로 선언해야 한다!!!

자료형에 제발 주의할 것

public class BOJ_9613 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(in.readLine());
		for(int i=0;i<t;i++) {
			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			int total = Integer.parseInt(st.nextToken());
			int arr[] = new int[total];
			long sum = 0;
			
			for(int x =0;x<total;x++) {
				arr[x] = Integer.parseInt(st.nextToken());
			}
			for(int j=0;j<total-1;j++) {
				for(int k=j+1;k<total;k++) {
					int a = arr[j];
					int b = arr[k];
					if(a<b) {
						int tmp = a;
						a = b;
						b = tmp;
					}
					sum += gcd(a,b);
				}
			}
			System.out.println(sum);
		}
	}
	static int gcd(int a, int b) {
		if(a%b == 0) return b;
		return gcd(b,a%b);
	}
}