ログイン
編集不可のページディスカッション情報添付ファイル
akky/cp/gcd-lcm

MMA

問題

最大公約数と最小公倍数の問題

概要

N個の数値の最小公倍数を求めよ

制約

N = 1..100
T_i = 1..10^18

問題URL

https://atcoder.jp/contests/abc070/tasks/abc070_c

コード

from functools import reduce
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

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

N = int(input())
T = [int(input()) for _ in range(N)]

print(reduce(lcm, T))

要点

  • gcdの計算量は小さい方の数をnとしたとき O(log(n))
  • lcm = a * b / gcd で求められる
  • reduceをimportする(python3)

参考

akky/cp/gcd-lcm (最終更新日時 2018-12-23 22:56:45 更新者 akky)