스승님 찾기

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	15979
문제명	스승님 찾기
레벨	실버 2
분류	애드혹
시간복잡도	O(logn)
인풋사이즈	n<=10^9
사용한 언어	Python
제출기록	32952KB / 72ms
최고기록	60ms
해결날짜	2022/06/01

풀이

(0,0)에서 (M,N)이 보인다는 것은 M과 N이 서로소라는 것.
따라서 gcd(M,N)이 1이면 한번에 순간이동 가능하다.
서로소가 아닐 경우에는 이렇게 두번만에 이동하는 것이 가능하다. (1,N-1), (M-1,1) 이렇게 두번 이동하는 셈인데 둘다 서로소니까 항상 이동 가능.
- (0,0) ⇒ (1,N-1) ⇒ (M,N)
M이나 N이 0일 경우에는 따로 처리해줘야 한다.
- 거리가 한칸일때는 보이므로 한번에 이동가능
- 거리가 2칸 이상일때는, 예를들어 (0,M)이면, (0,0)⇒(1,0)⇒(0,M) 으로 두번에 이동가능.
- 목적지가 (0,0)일때는 그냥 0을 출력
결국 모든 경우에 대해 답은 0,1,2중 하나이고, 이것은 gcd계산 한번으로 결정 가능. 시간복잡도는 O(logn)

코드

"""Solution code for "BOJ 15979. 스승님 찾기".

- Problem link: https://www.acmicpc.net/problem/15979
- Solution link: http://www.teferi.net/ps/problems/boj/15979

Tags: [Ad hoc]
"""

import math


def main():
    M, N = [int(x) for x in input().split()]
    if M == N == 0:
        print('0')
    elif M == 0 or N == 0:
        print('1' if abs(M - N) == 1 else '2')
    else:
        print('1' if math.gcd(M, N) == 1 else '2')


if __name__ == '__main__':
    main()

BOJ, 실버 2