Tag: euclidean algorithm

ring = list(map(int, input().split()))
first = ring[0]
rings = ring[1:]
def gcd(a, b):
    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

for r in rings:
    if first % r == 0:
        print(f"{first // r}/1")
    elif r % first == 0:
        print(f"1/{r // first}")
    else:
        g = gcd(first, r)
        print(f"{first // g}/{r // g}")

$a, b \in \mathbb{Z}$이고 $a$를 $b$로 나눈 나머지를 $r$이라 하자. ($b \leq a, 0 \leq r \leq b$)

$a, b$의 최대 공약수를 $(a, b)$라고 하면, 다음이 성립한다.

$(a, b)=(b, r)$

출처: wikipidia

$r$이 0이 될 때 알고리즘을 멈추며, 이 때의 $b$가 최대공약수가 된다.

예를 들어 1460과 1037에 대해 알고리즘을 진행해보면 다음과 같다.

$r$이 0일때 $b$가 4이므로 1460과 1037의 최대공약수는 4이다.