[アルゴリズム解答][Python]白駿1934号:最小公倍数

白駿1934題リンク:https://www.acmicpc.net/problem/1934

📑 問題の説明

2つの自然数(テストケース数とテストケース数に基づいて)が与えられた場合、プログラムは最小公倍数を求める.
入力:1行目はテストケース数、2行目は2つの自然数
出力:各テストエンクロージャの最小公倍数

💡 トラブルシューティング方法

最小公倍数の特性
n 1,n 2はタイミングを与え,2つの数の最大公約数がgcdであると仮定する.
n1 = gcd k1
n2 = gcd k2
はい.
n 1,n 2の最大公倍数は
lcm=gcdk1k2.

最大公約数を求める
2つの自然数が与えられた場合(n 1>n 2)、残りの演算を用いてgcdを求める.

1で求めた最大公倍数と最小公倍数の特性を用いて最小公倍数を求める

💻 コード#コード#

import sys


def lcm(a,b):
    num1 = a
    num2 = b
    if (a<b):
        tmp = a
        a= b
        b= tmp

    while(b!=0):
        n = a%b
        a = b
        b = n

    n1 = num1/a
    n2 = num2/a

    print(round(a*n1*n2))


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    for i in range(n):
        a, b = map(int, sys.stdin.readline().split())
        lcm(a,b)
© 2022 GitHub, Inc.
Terms

💟 詳細