[백준] 2168번 (python 파이썬)

https://www.acmicpc.net/problem/2168

 

사실 유클리드 호제법에 관련된 문제이다.

 

https://m.blog.naver.com/orbis1020/220664563768

 

위의 그림을 보고 알 수 있는것은

1.

대각선이 꼭지점을 지나가지 않는 직사각형은 x + y -1

대각선이 꼭지점을 지나가는 직사각형은 x + y -1 - (점의 개수)

이다.

 

2.

점의 개수는 어떻게 구하냐

x, y의 최대공약수 - 1이다

 

즉 점이 없는 직사각형들은 (x, y의 최대공약수 - 1) 을하면 0이 나오기 때문에 이도 성립한다

 

1, 2를 종합해보면

x + y - gcd(x, y) 라는 식을 구할 수 있다.

 

x, y = map(int, input().split(' '))


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

print(x + y - gcd(x, y))