結果

問題 No.2609 Decreasing GCDs
ユーザー maguroflymagurofly
提出日時 2024-01-19 21:56:42
言語 Ruby
(3.3.0)
結果
AC  
実行時間 616 ms / 1,000 ms
コード長 497 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 62,720 KB
最終ジャッジ日時 2024-01-19 21:56:59
合計ジャッジ時間 15,611 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 599 ms
62,720 KB
testcase_01 AC 588 ms
62,720 KB
testcase_02 AC 587 ms
62,720 KB
testcase_03 AC 570 ms
62,720 KB
testcase_04 AC 588 ms
62,720 KB
testcase_05 AC 584 ms
62,720 KB
testcase_06 AC 595 ms
62,720 KB
testcase_07 AC 568 ms
62,720 KB
testcase_08 AC 596 ms
62,720 KB
testcase_09 AC 557 ms
62,720 KB
testcase_10 AC 593 ms
62,720 KB
testcase_11 AC 567 ms
62,720 KB
testcase_12 AC 606 ms
62,720 KB
testcase_13 AC 585 ms
62,720 KB
testcase_14 AC 593 ms
62,720 KB
testcase_15 AC 571 ms
62,720 KB
testcase_16 AC 612 ms
62,720 KB
testcase_17 AC 561 ms
62,720 KB
testcase_18 AC 616 ms
62,720 KB
testcase_19 AC 596 ms
62,720 KB
testcase_20 AC 596 ms
62,720 KB
testcase_21 AC 594 ms
62,720 KB
testcase_22 AC 577 ms
62,720 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

require "prime"

S = 5
N = gets.to_i
primes = Prime.take(S + N - 1)
base_primes = primes[0, S]
base_qs = base_primes.map { |p|
	a = [1]
	x = p
	while x < 100000000
		a << x
		x *= p
	end
	a
}
bases = base_qs.inject { |x, y| x.product(y).map { |a, b| a * b } }
bases.sort!
gcds = primes[S, N - 1].reverse
A = [1] * N
(0 ... N - 1).each do |i|
	g = gcds[i]
	A[i] *= g
	A[i + 1] *= g
end
(1...N).each do |i|
	A[i] *= bases.find { |x| A[i - 1].gcd(x) == 1 && A[i - 1] < A[i] * x }
end
puts A.join(" ")
0