結果

問題 No.2609 Decreasing GCDs
コンテスト
ユーザー 👑 magurofly
提出日時 2024-01-19 21:56:42
言語 Ruby
(4.0.6 + ACL)
コンパイル:
ruby -w -c _filename_
実行:
ruby _filename_
結果
AC  
実行時間 426 ms / 1,000 ms
+ 334µs
コード長 497 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 391 ms
コンパイル使用メモリ 8,832 KB
実行使用メモリ 61,912 KB
最終ジャッジ日時 2026-09-05 12:10:38
合計ジャッジ時間 11,819 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

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