結果

問題 No.2609 Decreasing GCDs
ユーザー maguroflymagurofly
提出日時 2024-01-19 21:56:42
言語 Ruby
(3.3.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 755 ms
56,316 KB
testcase_01 AC 759 ms
56,352 KB
testcase_02 AC 773 ms
56,320 KB
testcase_03 AC 772 ms
56,316 KB
testcase_04 AC 772 ms
56,316 KB
testcase_05 AC 773 ms
56,432 KB
testcase_06 AC 775 ms
56,324 KB
testcase_07 AC 765 ms
56,224 KB
testcase_08 AC 769 ms
56,320 KB
testcase_09 AC 766 ms
56,452 KB
testcase_10 AC 767 ms
56,440 KB
testcase_11 AC 768 ms
56,436 KB
testcase_12 AC 767 ms
56,456 KB
testcase_13 AC 773 ms
56,356 KB
testcase_14 AC 785 ms
56,472 KB
testcase_15 AC 768 ms
56,448 KB
testcase_16 AC 778 ms
56,608 KB
testcase_17 AC 787 ms
56,456 KB
testcase_18 AC 774 ms
56,608 KB
testcase_19 AC 763 ms
56,480 KB
testcase_20 AC 763 ms
56,480 KB
testcase_21 AC 783 ms
56,504 KB
testcase_22 AC 769 ms
56,480 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