BOJ 14490번: 백대열

www.acmicpc.net/problem/14490

14490번: 백대열

아이디어:

유클리드 호제법.. 을 사용하여 최대공약수를 구하는 문제이다.

r = a%b

a = b

b = r

을 반복해서 b가 0이 되는 경우의 a가 최대공약수가 된다.

이 알고리즘을 알면 아주 간단히 풀 수 있는 문제이다. 이거 이산수학에서 배웠는데..ㅋㅋ

import sys

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

exp = sys.stdin.readline().rstrip()
for i in range(len(exp)):
    if (exp[i]==':'):
        n = int(exp[0:i])
        m = int(exp[i+1:])

num = gcd(n,m)
print("%d:%d" % (n//num, m//num))