[Backjunnode.js]boj 9613解答

1168 ワード
白駿 数学 テキストリンク
9613 GCD合計数量
質問する
n個の正の整数が与えられると、可能なすべてのGCDの和を求めるプログラムが作成される.
入力
第1行は、試験例の個数t(1≦t≦100)を与える.各テストボックスは1行で構成されています.各試験例には、個数n(1しゅつりょく
各テストボックスは、正しい可能性のあるすべてのGCDの和を出力します.
テストケース

  • 入力
    3
    4 10 20 30 40
    3 7 5 12
    3 125 15 25

  • しゅつりょく
    70
    3
    35
    • ソースコード
    const rl = require('readline').createInterface(process.stdin, process.stdout);

let input = [];

rl.on('line', (line) => {
  input.push(line.split(' ').map((x) => parseInt(x)));
}).on('close', () => {
  const testCase = +input.shift();
  let answer = '';

  for (let i = 0; i < testCase; i++) {
    answer += calc(input[i][0], input[i].splice(1)) + '\n';
  }

  console.log(answer);
});

function calc(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;
}

function gcd(x, y) {
  while (y) {
    [x, y] = [y, x % y];
  }

  return x;
}
    メモリ/時間
  • メモリ
    9464 KB
  • 時間
    208 ms
    • せきぶん
  • は全ペアのGCD値
    • を出力する.
    arrayメソッド
    Dockerを使用して高利用可能なETCDクラスタを展開する