양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.
각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.
사용 알고리즘: 유클리드 호제법
- 각 테스트 케이스마다 주어지는 수들을 배열에 저장하고 이중 for문을 이용해 가능한 모든 쌍에 대해 유클리드 호제법을 이용해서 gcd를 구해준 뒤 결괏값을 갱신한다
- n제곱의 시간복잡도
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
#include <math.h>
using namespace std;
// 유클리드 호제법
int GCD(int x, int y)
{
if (y == 0)
return x;
return GCD(y, x % y);
}
int main()
{
int T;
cin >> T;
// 각 테스트 케이스 마다
for (int i = 0; i < T; i++)
{
int n; // n 입력받기
cin >> n;
vector<int> vec;
// 주어진 수들 배열에 저장
for (int j = 0; j < n; j++)
{
int x;
cin >> x;
vec.push_back(x);
}
long long int result = 0; // 결과를 담을 변수
// 모든 쌍에 대해 gcd구해서 결과 갱신
for (int a = 0; a < (n-1); a++)
{
for (int b = a + 1; b < n; b++)
{
result += GCD(vec[a], vec[b]);
}
}
cout << result << '\n'; // 답안 출력
}
return 0;
}