백준 알고리즘 9613번 : GCD 합

링크

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

문제

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

입력

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

출력

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

예제 입력 및 출력

풀이 법

유클리드 호제법을 사용해서 최대 공약수를 구해주면 된다.
모든 쌍의 GCD의 합을 출력하라고 하였으므로 반복문을 2개 사용해서 모든 쌍을 대입해주면 된다(코드 상 divide함수) 다만 반환 자료형에 주의를 해야하는데 int형으로 하였을 때 오버 플로우가 발생하기 때문에(이걸 잘못해서 처음에 틀림...) long long형으로 반환해주었다.

풀이 코드

// 9613번 : GCD 합

#include <stdio.h>
#include <stdlib.h>
#define ll long long

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b, a % b);
}

ll divide(int n, int list[])
{
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j)
            {
                continue;
            }
            else
            {
                sum += gcd(list[i], list[j]);
            }
        }
    }
    return sum;
}

int main()
{
    int test;
    scanf("%d", &test);
    while (test--)
    {
        int n;
        scanf("%d", &n);
        int *list;
        list = (int *)malloc(sizeof(int) * n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &list[i]);
        }
        printf("%lld\n", divide(n, list) / 2);
        free(list);
    }
    return 0;
}