[1735] 분수합 in python

 

> 유클리드 호제법

 

 

최대 공약수를 구할 땐

유클리드 호제법을 이용해야 한다.

 

 

* 유클리드 알고리즘 *

: a, b의 최대 공약수는 (a-b),b의 최대공약수와 같다.

1. 임의의 두 자연수 a,b가 주어졌다.

2. 두 자연수 중에 큰 값을 a라고 가정한다.

3. 큰 수 a 자리에는 a-b와 b값 중에 큰 값을 넣는다.

작은 수 b 자리에는 a-b와 b값 중에 작은 값을 넣는다.

그리고 재귀함수를 호출한다.

 

 

import sys

sys.setrecursionlimit(100000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(max(a - b, b), min(a - b, b))


c1, p1 = map(int, input().split())
c2, p2 = map(int, input().split())
c = c1 * p2 + c2 * p1
p = p1 * p2
m = gcd(max(c, p), min(c, p))
print(c//m,p//m)