9613번

9613번 - GCD 합

최대공약수 응용문제,

아마 유클리드 호제법이 아닌 방법으로 풀면 시간초과가 날 것 같다.

유클리드 호제법을 이용해서 문제를 풀었다.

정답은 int 형 범위를 넘을 수 있으므로 유의!

유클리드 호제법

- A,B 라는 숫자가 있을 때, 

GCD(A,B)=GCD(B,B%A) (단, B%A가 0 이면 B가 최대공약수가 된다.)

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
 
int gcd(int a,int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a%b);
    }
}
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int n;
        long long ans = 0;
        vector<int> v;
 
 
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int tmp;
            cin >> tmp;
            v.push_back(tmp);
        }
 
        for (int i = 0; i < v.size()-1; i++)
        {
            for (int j = i + 1; j < v.size(); j++)
            {
                ans += gcd(v[i], v[j]);
            }
        }
 
        cout << ans << endl;
    }
 
    return 0;
}