【AtCoder-Ruby】ABC103 C - Modulo Summation

問題

問題文

N 個の正整数 a1, a2,..., aN が与えられます。
非負整数 m に対して、 f(m) = (m mod a1) + (m mod a2) + ... + ( m mod aN) とします。
ここで、 X mod Y は X を Y で割った余りを表します。
f の最大値を求めてください。

制約

• 入力は全て整数である
• 2 ≤N ≤3000
• 2 ≤ai ≤10**5

問題リンク

考えたこと

最大は (a1 - 1) + .. + (an - 1) だが、
このような m があるかどう証明する？

神のお告げはを聞こう。

最小公倍数を LCM で表すことにして

• M = LCM(a1,a2,…,aN)−1 が条件を満たす。あるいは単に
• M=a1a2…aN−1 でもよい。

出典: けんちょんの競プロ精進記録

そうなんだ。

例題で確かめてみる。

[14:37:37 ~]$ irb
>> dividend = [7, 46, 11, 20, 11].inject(:lcm) - 1
=> 35419
>> [7, 46, 11, 20, 11].each { |n| puts dividend % n }
6
45
10
19
10
=> [7, 46, 11, 20, 11]
>>

確かにその通りでした。

回答

N = gets.strip.to_i
puts gets.strip.split.map(&:to_i).inject(:+) - N

考察

多分本番ではこれ系の問題はすぐに出てこない。
とりあえず、多く問題を解こう。