BOJ 9613. GCD 합

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	if (b == 0)return a;
	else return gcd(b, a % b);
}


int main()
{
	int n,t;
	
	cin >> t;
	for (int i = 0; i < t; i++)
	{	
		int arr[101];
		cin >> n;
		for (int j = 0; j < n; j++) {
			cin >> arr[j];
		}

		long long sum = 0;
		for (int y = 0; y < n; y++)
		{
			for (int x = y; x < n; x++)
			{
				sum += gcd(arr[y], arr[x]);
			}
		}
		cout << sum << "\n";
	}


	return 0;
}

 

10	20	30	40
20	30	40
30	40
40

a[0] + a[1] + a[2] + a[3]

a[1] + a[2] + a[3]

a[2] + a[3]

-> 두 수간의 최대공약수 합을 구해야함으로 마지막에 혼자 남을경우에는 계산 불가

i는 0 부터 n-1 까지, j는 i+1부터 n까지(해당 숫자의 다음 숫자부터 끝까지 더해야함)