競技プログラミングをpythonで遊ぶ3[ABC103 C]

コンテストページはこちら↓

C - Modulo Summation

C問題なので長めです！

問題文
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

要約
ある数(m)をN個の数字(ai)でそれぞれ割った余りを全部足した時の最大値
タイトルの剰余加算そのままの意味
例3, 4, 6だと、f(11) = (11 mod 3) + (11 mod 4) + (11 mod 6) = 10が最大
最小公倍数-1を剰余すればよさそう

解答

N = int(input())
a = list(map(int, input().split()))

# 最大公約数(greatest_common_divisor)
def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a%b)

# 最小公倍数(lowest_common_multiple)
def lcm(a, b):
  return a*b//gcd(a,b)

# 最小公倍数と、比べていない数字を比べ、最小公倍数を更新する
alcm = a[0]
for i in a[1:]:
  alcm = lcm(alcm, i)

res = 0

# 関数f
for i in range(N):
  res += (alcm-1) % a[i]

print(res)

参考サイトより最小公倍数の求め方を得る

3つ以上の数の最大公約数と最小公倍数 - Qiita

>>> def gcd(a, b):
...   if b == 0:
...     return a
...   return gcd(b, a%b)
...
>>> def lcm(a, b):
...   return a*b//gcd(a,b)
...
>>> lcm(3, 4)
12
>>> lcm(12, 6)
12

ユークリッドの互除法強い
gcdは関数の中で自分を呼び出す再起関数と呼ばれる関数

(問題) 1071 と 1029 の最大公約数を求める。
・1071 を _1029_ で割った余りは 42
・_1029_ を 42 で割った余りは _21_
・42 を _21_ で割った余りは 0
よって、最大公約数は_21_である。

二つの数字(A, B)から導いた結果(C)を使い、同じ計算をしたいときに再起関数を使おう
A%B = C -> B%C = D -> C%D = E

def greatest_common_divisor(a, b):
    if b == 0:
        return a
    return greatest_common_divisor(b, a%b)

でも、今回の困りどころはここではない。

def lcm(a, b):
  return a*b//gcd(a,b)

こいつの//が一番必要だった。

>>> a = 1
>>> for i in range(70):
...  a *= 99999
...
>>> a
99930024144526916773982970399819677006243826886851248341949435103502365016928159377373102412011786789305356470125308992723524935236237526395803543836650152878130690276548112184320708075952847523963238291960759583049646185441496518267798819550433944907832048337650154662071958518735840420131076787388165843389322659115863969951689445260024149993000001
>>> a / 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: integer division result too large for a float

理由はこれ、とてつもなく大きい数を普通に割るとfloat型になるときにエラーを吐くのだ...
最大3000個の100000まであり得る数を使うため、それでは困る
そこで、少数のことは考えずに、割ってint型で返してくれる//を使った

>>> a // 1
99930024144526916773982970399819677006243826886851248341949435103502365016928159377373102412011786789305356470125308992723524935236237526395803543836650152878130690276548112184320708075952847523963238291960759583049646185441496518267798819550433944907832048337650154662071958518735840420131076787388165843389322659115863969951689445260024149993000001
>>> 5 / 2
2.5
>>> 5 // 2
2
>>> 100 / 2
50.0
>>> 100 // 2
50

エラー解消！

以上！