1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

【Ruby】ARC114 A問題 解法メモ

Last updated at Posted at 2021-03-15

AtcoderRegularContest114のA問題の解法メモです。

自分のようなこれからエンジニアになる人間でも納得できる簡単な考え方がひらめいたので残します。

公式の解説のように全探索しました。
50までの素数[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]15コを掛け合わせて作れる整数2**15コのうち、すべてのXiが最小公約数1にならない値の最小値が答えになります。


# ARC114
# A
require 'prime'
N = gets.to_i
X = gets.split.map &:to_i

# 50までの数字のうち素数のみをprimeに格納(全部で15コ)
prime = []
Prime.each(50){|i| prime<<i}

# 上記15コの素数のうち、掛け合わせて作れるすべての値をpprimeに格納
pprime = []
1.upto(15) do |i|
  combi = prime.combination(i).to_a
  combi.each do |j|
    pprime << j.inject(:*)
  end
end
pprime.sort!

# pprimeに格納されている整数のうち、Xすべてと最小公約数が1にならない最小値がanswer
ans = 0
pprime.each do |i|
  if X.all?{|e| e.gcd(i) != 1}
    ans = i
    break
  end
end

puts ans
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?