출처 BOJ

GCD 합

문제

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

입력

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

출력

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

예제

범위체크

100개 수가 모두 1,000,000라고 가정,
모든 쌍의 개수 : $100C2 = {100 * 99 \over 2 * 1}$
모든 쌍의 GCD합 = $100C2 * 10^6 = {99 \over 2} * 10^8 \ge INT$
→ long long 사용

풀이

GCD구하는 간단한 방법 : 유클리드 호제법
if a > b,
GCD(a,b) = GCD(a-b,b)
= GCD(b,a%b) ← 당연히 위보다 반복횟수가 더 적음

코드

code

#include<cstdio>
//#include<iostream>

using namespace std;

int arr[101];

int getGCD(int a, int b){
	if(b==0)
		return a;
	else
		return getGCD(b,a%b);
}

int main(){
	int testcase;
	scanf("%d",&testcase);
	while(testcase--){
		long long sum = 0;
		int len;
		scanf("%d",&len);
		for(int i=0; i<len; i++){
			scanf("%d",&arr[i]);
		}

		for(int i=0; i<len-1; i++){
			for(int j=i+1; j<len; j++){
				sum += getGCD(arr[i],arr[j]);
			}
		}
		printf("%lld\n",sum);
	}
}

복잡도

$O(log(a+b))$

증명 )
$a \ge b$ 일떄,
gcd(a,b) → gcd(b, a%b) → gcd(a%b, b%(a%b)) — 상수 연산
a = xm + n%m
xm > n%m
xm + n%m > 2(n%m)
n > 2(n%m)
n → n%m은 절반이하가 됨

따라서, $O(log(max(a,b)))$라고 할 수 있고
간단하게 표현하면 max(a,b)는 a+b보다 작으므로
→ $O(log(a+b))$