백준 1735 분수 합 파이썬

1735번: 분수 합 (acmicpc.net)

1735번: 분수 합

유클리드 호제법이라는 것이 있다.

앞서 말한 최대공약수 공식보다도 시간초과가 덜 되는 코드이다.

a 를 b로 나눈 나머지가 0이 아닐 때마다 나누는 수를 갱신하고 a를 b로, b를 나누는수로 갱신하면서 마지막에 b를 출력하면 최대공약수가 된다.

import sys
input = sys.stdin.readline
def gcd(a, b):
    while a % b != 0:
        mod = a % b
        a = b
        b = mod
    return b
a, b = map(int, input().split())
c, d = map(int, input().split())
g = gcd(a * d + b * c, b * d)
print((a * d + b * c)//g, (b * d)//g)