AtCoder BC103 C: Modulo Summation

問題

C - Modulo Summation
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

m mod ai が最大になるのは、mがaiの倍数-1の時で、余りはai-1になる。

よって、mがa1,a2,,,anの最小公倍数-1の時にf(m)は最大になる。

最大値を求めるだけなら最小公倍数自体は求める必要は無く、ai-1の総和を求めれば良い。

(最初、mを求める問題かと思い、最小公倍数を求めるコードを書いてしまって時間ロス。。。)

実装

n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

ans = 0
a.each do |v|
    ans += v - 1
end
puts ans

コメント

タイトルとURLをコピーしました