백준 9613 - GCD 합

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

9613번: GCD 합

 

풀이

 

GCD란 최대공약수로, 유클리드 호제법을 이용하여 구할 수 있다.

두 수를 계속 나누어서 생기는 나머지가 0이 될때까지 계산하는 과정을 계속 반복한다.

코드로 나타내면 아래와 같다. 이 때 a가 최대공약수가 된다.

while(b!=0)
    {
        n=a%b;
        a=b;
        b=n;
    }

주의할 점은 합이 int 범위를 넘어설 수 있으므로 long으로 지정해줘야 한다.

 

코드

#include <iostream>
using namespace std;

int gcd(int a, int b);

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        long cnt=0;
        int* arr = new int[a];
        for(int j=0; j<a; j++)
        {
            int b;
            cin>>b;
            arr[j]=b;
        }
        for(int j=0; j<a; j++)
        {
            for(int k=j+1; k<a; k++)
            {
                cnt+=gcd(arr[j],arr[k]);
            }
        }
        cout<<cnt<<'\n';
    }
}

int gcd(int a, int b)
{
    int n;
    if(a<b) swap(a,b);
    while(b!=0)
    {
        n=a%b;
        a=b;
        b=n;
    }
    return a;
}