백준 2168번 : 타일 위의 대각선

문제

한 변의 길이가 1cm인 정사각형 모양의 타일이 있다.

이 타일들을 가로가 xcm, 세로가 ycm인 직사각형 모양의 벽에 빈틈없이 붙였다.

x와 y는 정수이다. 이 직사각형에 하나의 대각선을 그렸다.

직사각형에 붙어 있는 x*y개의 타일 중에는 대각선이 그려진 타일도 있고, 그렇지 않은 타일도 있다.

x*y개의 타일 중에서 대각선이 그려져 있는 타일의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 가로의 길이 xcm와 세로의 길이 ycm가 주어진다. x와 y는 1,000,000,000 이하의 자연수이다.

x와 y 사이에는 빈칸이 하나 이상 있다.

출력

첫째 줄에 대각선이 그려져 있는 타일의 개수를 출력한다.

---

예제 입력 1

8   12

예제 출력 1

16

---

해결 방법

타일 위에서의 직선을 생각해보았을 때, 좌표 값이 (정수, 정수)로 나왔을 경우에 아닌 경우보다 1칸을 아낄 수 있다.

그렇기 때문에 A + B - gcd(A,B) 로 연산을 하면 원하는 값을 얻을 수 있다.

PyPy3로 제출하였고, 메모리 : 121220 KB    시간 : 100 ms

소스 코드

def gcd(A,B):
    mod = A % B
    while mod > 0:
        A = B
        B = mod
        mod = A % B
    return B
    
x,y = map(int, input().split())

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