競プロ典型90問 Large LCM(★3)コード解説
はじめに
本日はM1グランプリでしたね!私はYoutubeに上がっている動画を1回戦からすべて見てるくらいM1が好きですので、今年の楽しく拝見させていただきました!
ウエストランドのお二方、本当におめでとうございます!!
失礼ですが始まる前は正直優勝するとは思いませんでした…。以前からの悪口の勢いとあるなしクイズのフォーマットがマッチしててとても聞きやすくて密度の高い5分間でした!
正直、M1で満足してお休みモードなので今日はブログの更新を休もうと思ったんですけど、こういうのは1日でも休んだら気持ちが緩むので、気合を入れてやっていきます!
今回も競プロ典型90問の★3問題です。
競プロ典型90問
038 - Large LCM(★3)
最小公倍数を求めて、それが10^18
より大きければLarge
を出力するといった問題です。
考え方自体は簡単だと思いますが、競プロだし、なんかあるんでしょ~?と思われる方もいらっしゃると思いますが、実はPythonだと、とてもシンプルなコードで書くことが出来ます。
import math a, b = map(int, input().split(" ")) lcm = a*b // math.gcd(a, b) if lcm > 10**18: print("Large") else: print(lcm)
まず、math
モジュールを用いて、最小公倍数はmath.lcm
で求めることが出来ます。が、Atcoderではエラーが出力されました。ですので代わりの手法で最小公倍数を求める必要があります。
最小公倍数は最大公約数math.gcd
を用いて、以下の式で表すことが出来ます。
lcm(a, b) = a*b // gcd(a, b)
それが1018より大きいか小さいかを判断して答えを出力します。ここがポイントで、Pythonは多倍長変数と言ってめちゃくちゃ長い数値を扱える言語なので、このまま判定することが出来ます。
しかし言語によってはオーバーフローして計算できないため、工夫する必要があるらしいです。私はPython以外はほとんどわからないので、気になった方は調べてみてください。
おわりに
今回はPython勢にとって有利すぎる問題でしたね。
今から見損ねた敗者復活戦の動画を見ますので、今日はこの辺で…。お疲れ様でした。