マスター・オブ・整数で競技プログラミング その３

３　最小公倍数と最大公倍数

最小公倍数と最大公約数の利用

• たてＡ cm, 横Ｂ cm, 高さＣ cmの直方体がたくさんある。この箱を隙間なく並べて立方体を作る。作ることができる最小の立方体の1辺の長さを求めよ。

Ａ,Ｂ,Ｃの最小公倍数を求めればよい。最小公倍数や最大公約数を手計算で求める際は，素因数分解して素因数と指数を見てやれば求めることができるがプログラミングしようとするとめんどくさいので，以下のように行う。

A，Bの最小公倍数を,最大公約数をとする。

1. ユークリッドの互除法を利用して最大公約数を求める。
2. を利用してを求める。

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

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

A = int(input())
B = int(input())
g = gcd(A,B)
l = lcm(A,B)

３つの数Ａ，Ｂ，Ｃに対して最小公倍数（最大公約数）を求める場合はまず，任意の2数（Ａ，Ｂ）に対して最小公倍数Ｌ１を求める。Ｌ１とＣに大して最小公倍数を求めればそれが，Ａ，Ｂ，Ｃの最小公倍数である。

A = int(input())
B = int(input())
C = int(input())
l1 = lcm(A,B)
l = lcm(l1,C)

• 直方体が全部でN個しかない場合に作ることができる最大の立方体の1辺の長さを求めよ。 最小の立方体を作るのに必要な直方体の数を求める。各辺の方向にいくつ直方体を並べるかを数えればよいので，

最小公倍数をＬとしたとき，

が必要な直方体の個数である。 最大の立方体を作るには最小の立方体を縦，横，高さの3方向に同じ数ずつ並べて作ることができるので一方向に並べる最小の立方体の個数をx個とすると，

が成り立つ。これをみたす最大の整数 に対しが求めたい最大の立方体の1辺の長さである。

N = int(input()) #直方体の個数
l1 = lcm(A,B)
L = lcm(l1,C)
M = L//A * L//B * L//C
x = int( (N/M) ** (1/3) )
print(L*x)