백준 9613 - GCD 합

문제 설명 

 

 

 

=> 유클리드 호제법으로 최대공약수를 구할 수 있는 지에 대한 문제이다. 
=> 유클리드 호제법 코드는 아래와 같다. 

int GCD (int A, int B) //function that find GCD
{
    while(B!=0)
    {
        int tmp=B;
        B=A%B;
        A=tmp;
    }
    return A;
}

 

=>위 함수를 이용하고 가능한 모든 쌍을 해당 함수를 통해 값을 구하면 된다. 

 

 

*** 값의 범위가 int인지 long인지 정확히 인지할 필요가 있다. 

 

 

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> possiblePair;

int GCD (int A, int B) //function that find GCD
{
    while(B!=0)
    {
        int tmp=B;
        B=A%B;
        A=tmp;
    }
    return A;
}

long findPossible() //fuction that find sum of all GCDs
{
    long answer=0;
    int limit=possiblePair.size();
    
    for(int i=0; i< limit; ++i)
    {
        for(int j=i+1; j<limit; ++j)
        {
            answer+= GCD(possiblePair[i], possiblePair[j]);
        }
    }
    return answer;
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N; // Input Number
    while(N>0)
    {
        int testcase; // Count of testcase number
        cin >>testcase;
        int tmp;
        for(int i=0; i<testcase; ++i)
        {
            cin >>tmp;
            possiblePair.push_back(tmp);
        }
        cout <<findPossible()<<'\n';
        possiblePair.resize(0);
        N--;
    }
    
    return 0;
}