[백준][Node.js] 9613번 : GCD 합

 

 

Algorithm

-  GCD 합 -

 

---

 

문제

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

 

입출력 예시

 

문제 풀기

const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];
rl.on("line", function (line) {
	input.push(
		line
			.toString()
			.split(" ")
			.map((el) => +el)
	);
}).on("close", function () {
	input.shift();
	let result = [];

	for (let i = 0; i < input.length; i++) {
		result.push(findValue(input[i][0], input[i].splice(1)));
	}
	console.log(result.join("\n"));
	process.exit();
});

let findValue = (a, b) => {
	let sum = 0;

	for (let i = 0; i < a - 1; i++) {
		for (let j = i + 1; j < a; j++) {
			sum += gcd(b[i], b[j]);
		}
	}
	return sum;
};

let gcd = (x, y) => {
	while (y) {
		[x, y] = [y, x % y];
	}
	return x;
};