[BJ / 9613] GCD 합

문제

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

입력

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

출력

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

예시

풀이

조합을 구하는 함수와, gcd를 구하는 함수를 모두 구현한 다음 각자 조합의 gcd를 전부 더하는 방식으로 구현했다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
rl.on('line', (line) => {
  input.push(line);
});

rl.on('close', () => {
  let array = Array.from({ length: input[0] });
  for (let i = 0; i < input[0]; i++) {
    array[i] = input[i + 1]
      .split(' ')
      .map((el) => parseInt(el))
      .filter((v, i) => i !== 0);
  }
  console.log(solution(array));
});

function solution(nums) {
  let answer = '';
  let combination = [];
  for (let i = 0; i < nums.length; i++) {
    combination.push(getCombination(nums[i], 2));
  }

  combination.forEach((v) => {
    let temp = 0;
    v.forEach((v1) => {
      temp += getGCD(v1[0], v1[1]);
    });
    answer += temp + '\n';
  });

  return answer;
}

let getCombination = (numArray, pick) => {
  if (pick === 1) return numArray.map((el) => [el]);

  let combinations = [];

  numArray.forEach((v, i) => {
    const smallerCombination = getCombination(numArray.slice(i + 1), pick - 1);
    smallerCombination.forEach((combination) => {
      combinations.push([v].concat(combination));
    });
  });
  return combinations;
};

let getGCD = (num1, num2) => {
  let [b, s] = num1 > num2 ? [num1, num2] : [num2, num1];

  while (b % s !== 0) {
    [b, s] = [s, b % s];
  }
  return s;
};