백준 9613번: GCD 합

https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

 

 

 

문제

 

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

 

 

 

입력

 

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

 

 

 

출력

 

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

 

 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int gcd(int x, int y){	
	int temp, r;
	
	if(y>x) {
		temp=x;
		x=y;
		y=temp;
	}

	while(1) {
		r=x%y;

		if(r==0)
			return y;
		else {
			temp=y;
			y=x%y;
			x=temp;
		}
	}
}

int main(){
	int t;

	cin>>t;
	for(int i=0; i<t; i++) {
		int n;
		cin>>n;

		vector<int> vec(n);
		for(int j=0; j<n; j++) cin>>vec[j];

		long long sum=0;
		for(int k=0; k<n-1; k++)
			for(int l=k+1; l<n; l++)
				sum+=gcd(vec[k], vec[l]);

		cout<<sum<<endl;
	}
}