lcmについて
- lcm(最小公倍数)はgcdから導ける
lcm = a*b/gcd(a,b)
- gcdがユークリッド互除法を用いるので非常に計算結果は早い
実装
def lcm(m, n):
return m//math.gcd(m, n)*n
例; 非常に大きな分数の最小公倍数を求める
問題
解説
複数の巨大な数の分数の最小公倍数を求めようとすると桁あふれする
このとき、3stepに分けるとうまく処理できる
- 分母(v)の数字全体のgcd(vg)を求める
- 分子(d)の数字全体のlcm(dl)を求める
- 各々の要素に対して、(v//vg*dl//d)が解になる
解答
import decimal
import functools
import math
def lcm(m, n):
return m//math.gcd(m, n)*n
def run():
N=int(input())
if N == 0:
exit()
DV = []
for _ in range(N):
d,v=map(int,input().split())
# 1. time = d/v 小数点になってしまうで普通には処理できない
# 2. 大きい数なのでgcdで減らす
g = math.gcd(d,v)
d,v = d//g, v//g
DV.append( (d,v) )
# 3. vの最小公倍数
vg = functools.reduce(math.gcd, [v for d,v in DV])
# 4. dの最大公倍数
dl = functools.reduce(lcm, [d for d,v in DV])
# 5. dump
for d,v in DV:
print(v//vg*dl//d)
while 1:
run()