この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/2193fbb57ab66237ed9e
次：https://qiita.com/sano192/items/fee4234d2942ea6c02a5
【目標】
・最小公倍数を求められるようになる
【概要】
単純に2数の最小公倍数を求めることができれば解ける問題。この問題では最小公倍数を求めるアルゴリズムを実装できれば十分だが、一応【実装】のあとに【証明】として数学的な理屈も説明している。興味がある人は読んでもよいが無理に理解する必要はない。
【方針】
A、Bの両方で割り切れる最小の数＝A、B両方の倍数で最小のもの。
つまりA、Bの最小公倍数を出力すれば終わり。
では最小公倍数はどのように求めるか。
最小公倍数の求め方を知らない場合、自力で求め方を考えず、さっさとgoogleで「最小公倍数 python」と検索し、コードをコピペして解こう。検索すると以下のようなコードが出てくるだろう。
「lcm(x,y)：x,yの最小公倍数を返す」
import math
def lcm(x,y):
return (x*y)//math.gcd(x,y)
lcmは最小公倍数=least common multipleの頭文字。
import mathという部分は標準ライブラリというものを使っている。
ライブラリがなにかを説明するとややこしいが、競技プログラミングにおいては呪文のようなものだと理解しておけば十分だ。
最初にimport mathを唱えておくとmath.○○という形でsin,cos,tan,log,gcdなどの関数を使うことができる。単にgcd(x,y)と書くとエラーになるので必ずmath.gcd(x,y)と書くこと。
math.gcd(x,y)は「x,yの最大公約数を返す」関数。
gcdは最大公約数=greatest common divisorの頭文字。
つまり
return (x*y)//math.gcd(x.y)
は
(x*y)//(x,yの最大公約数)
を計算して返している。
そしてこれこそがx,yの最小公倍数となる。
「例」
12と18の最小公倍数
12、18の最大公約数は6。計算式に当てはめると
(12×18)/6=36
と求められる。36は12と18の最小公倍数。
【実装】
最小公倍数を求める関数ができていればA、Bを受け取ってA、Bの最小公倍数を出力するだけ。
import math
def lcm(x,y):
return (x*y)//math.gcd(x,y)
A,B=map(int, input().split())
print(lcm(A,B))
【証明】
なぜ最小公倍数が(x*y)//(x,yの最大公約数)で求まるのか証明を書く。
ガチガチの数学であるため、興味がなければここは飛ばしても構わない。
(証明)
A,Bの最大公約数をG、最小公倍数をLとする。
GがA、Bの最大公約数であるから、互いに素な数a、bを使って以下のように表せる。
A=aG...(1)
B=bG...(2)
LがA、Bの最小公倍数であるから、自然数n、mを使って以下のように表せる。
L=An…(3)
L=Bm..(4)
(3)、(4)に(1)、(2)を代入すると
L=aGn...(5)
L=bGm
ゆえに
aGn=bGm
両辺をGで割り
an=bm
a,bは互いに素であるからn=b,m=aとなる。
((n,m)=(b,a),(2b,2a),(3b,3a),...のどれでも等号は成り立つが、Lが「最小」公倍数であるから(n,m)=(b,a)となる)
n=bを(5)に代入すると
L=aGb
両辺にGを掛けて
GL=aG×bG
(1)、(2)を右辺に代入し、
GL=A×B
L=(A×B)/G
(証明終)
他に素因数分解を一般に当てはめたような証明方法もあるのでリンクを載せておく。上記の証明がしっくり来なければ見てみると良い。
https://manabitimes.jp/math/1032
【コード全文】
import math
def lcm(x,y):
return (x*y)//math.gcd(x,y)
A,B=map(int, input().split())
print(lcm(A,B))
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/2193fbb57ab66237ed9e
次：https://qiita.com/sano192/items/fee4234d2942ea6c02a5