[백준 9613] GCD 합 (C#, C++) - soo:bak

문제 링크

9613번 - GCD 합

설명

주어진 수들 중 서로 다른 두 수를 고르는 모든 경우에 대해 최대공약수를 구하고, 그 합을 출력하는 문제입니다.

접근법

수의 개수가 최대 100개이므로 모든 쌍을 확인해도 충분합니다. 이중 반복문으로 모든 쌍을 순회하면서 유클리드 호제법으로 최대공약수를 구해 누적합니다. 합이 커질 수 있으므로 64비트 정수를 사용합니다.

---

Code

C#

using System;

class Program {
  static long Gcd(long a, long b) {
    while (b != 0) { var t = a % b; a = b; b = t; }
    return a;
  }

  static void Main() {
    var t = int.Parse(Console.ReadLine()!);
    while (t-- > 0) {
      var parts = Console.ReadLine()!.Split();
      var n = int.Parse(parts[0]);
      var arr = new long[n];
      for (var i = 0; i < n; i++) arr[i] = long.Parse(parts[i + 1]);

      var sum = 0L;
      for (var i = 0; i < n; i++)
        for (var j = i + 1; j < n; j++)
          sum += Gcd(arr[i], arr[j]);

      Console.WriteLine(sum);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;

ll gcd(ll a, ll b) {
  while (b) { ll t = a % b; a = b; b = t; }
  return a;
}

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

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vll a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll sum = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
        sum += gcd(a[i], a[j]);
    cout << sum << "\n";
  }

  return 0;
}