結果

問題 No.2609 Decreasing GCDs
ユーザー magurofly
提出日時 2024-01-19 21:56:42
言語 Ruby
(3.4.1)
結果
AC  
実行時間 787 ms / 1,000 ms
コード長 497 bytes
コンパイル時間 92 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 56,608 KB
最終ジャッジ日時 2024-09-28 04:24:00
合計ジャッジ時間 19,633 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
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