Math 05最小公倍数(1934)

5090 ワード
python silver5 baekjoon algorithm テキストリンク

Math 05最小公倍数(1934)


質問する


2つの自然数AとBについて、Aの倍数でありBの倍数である自然数をAとBの公倍数と呼ぶ.この公倍数の中で最小の数を最小公倍数と呼ぶ.例えば、6及び15の公倍数は30、60、90等であり、最小公倍数は30である.
2つの自然数AとBが与えられた場合、AとBの最小公倍数を求めるプログラムを作成してください.

入力


第1行は、試験例の個数T(1≦T≦1000)を与える.2行目からT行にまたがり、AとBが与えられる.(1 ≤ A, B ≤ 45,000)

しゅつりょく


1行目から、T行入力AとBの最小公倍数の順に1行ずつ出力します.

に答える

  • ゲートタイムアウト

  • ゲートタイムアウト

  • 数学ライブラリ

    もちろん正しい
  • 前に学んだユークリッド号材料法
    ユークリッド号製法とは、
    数字a,bがある場合、aをbの残りとbで割った最大公約数は、aとbの最大公約数が等しいことを意味する.
    では、aをbで割って、bをaで割った残りの部分をbに代入し続けます.
    bが0に繰り返されると、残りのa値が最大公約数となる.

    • コード#コード#

    import sys
sys.stdin = open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()

N = int(input())

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

def lcm(a, b):
    return a * b / gcd(a, b)
# (최소공배수 x 최대 공약수) = `gcd^2 * m * n [m, n은 서로수]` => a * b
# 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.

for i in range(N):
    a, b = map(int,input().split())
    print(int(lcm(a,b)))

    #유클리드 호제법이란,
#숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의 최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.

#그럼, 계속해서 a 를 b로 나누어서 b를 a에 나눈 나머지를 b 에 대입시켜서 
# b 가 0이 될때 까지 반복을하면, 남는 a 값이 바로 최대 공약수 이다.

    学識


    ユークリッドアークほう

    コメント

    白駿9020-金バッハの推測
    Struts 2ログインブロック