int와 long의 차이

둘 다 정수를 저장하지만 저장 범위에 차이가 있다.

1. int : -2^31 2^31-1 (-2,147,483,647 +2,147,483,647)

2. long : -2^63 ~2^63 (얼마나 큰지 수를 표현하기 힘듦)

어떤 문제에서 TC 갯수 t (1<=t<=100), 각 TC는 수의 갯수가 주어지고 (1<n<=100), 그 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

문제 : 각 TC마다 가능한 모든 쌍의 GCD 합을 출력하시오.

입력 : 3 4 10 20 30 40 3 7 5 12 3 125 15 25

출력 : 70 3 35

입력으로 주어지는 수가 1,000,000을 넘지 않으므로 두 수 GCD는 1,000,000보다 작거나 같다.

수 1쌍에 GCD가 하나씩 나오고 쌍의 갯수는 nC2 = n(n-1)/2이고, 모든 쌍의 GCD가 1,000,000이라면 (100x99/2 ) x 1,000,000 = 4,950,000,000이다. 이것은 int형이 저장할 수 있는 최댓값 범위(2,147,483,647)를 벗어나므로 GCD합을 저장할 때는 long형 자료형을 사용해야 한다.