백준 9613 c++ GCD합

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

9613번: GCD 합

#include <iostream>
using namespace std;


long long gcd(long long a, long long b)//최대공약수gcd 구하는 함수
{
	if (b > a)//b가a보다 크다면 위치를 바꿔준다
	{
		long long tmp = a;
		a = b;
		b = tmp;
	}
	if (b == 0)//만약 나머지가 0이 된다면 a를 return한다
	{
		return a;
	}
	else//나머지가 0이 아니라면 함수 계속 반복
	{
		return gcd(b, a % b);
	}
}

int main()
{
	long long num;
	cin >> num;//gcd의 합 구하는걸 몇 번 반복할지
	while (num--)
	{
		long long count;
		cin >> count;
		long long array[100000];//수를 담을 배열
		long long result = 0;
		for (long long i = 0; i < count; i++)//배열에 값 입력
		{
			cin >> array[i];
		}
		for (long long i = 0; i < count-1; i++)//첫번째 수 일 때 부터
		{
			for (long long k = i + 1; k < count; k++)//그 다음 수부터 끝까지 비교
			{
				result+=gcd(array[i], array[k]);//gcd함수로 최대공약수 더해서 result에 더해서 저장
			}
		}
		cout << result << '\n';
	}

}

 

두 수의 최대공약수는 재귀함수로 간단하게 구할 수 있다.

작은수로 큰 수를 나누었을 때 나머지가 0이 될 때 까지 나누는 것을 계속 반복하고 나머지가 0이 될 때

작은 수가 최대 공약수가 된다.