게임의 신

시간 제한2초메모리 제한1024 MB

요약
X보다 크고 Y 이하인 수 중 X와 서로소인 수로 X를 바꾸는 게임을 두 사람이 번갈아 하며, 더 이상 바꿀 수 없는 사람이 진다.
난이도

보통10점 중 6점

유형
게임 이론, 수학, 정수론, 동적 계획법
정답자
아직 제출이 없습니다

문제

혁준이와 익준이는 게임을 아주 좋아한다!

현존하는 모든 게임을 섭렵한 두 사람은 더 이상 할 게임이 없어 방황하다가 결국 직접 게임을 만들어서 하기로 했다.

두 사람이 만든 게임은 아래 과정으로 진행된다.

  • 화면에 두 양의 정수 XX, YY가 표시된다.
  • 혁준이와 익준이가 번갈아 가며 XX보다 크고 YY보다 작거나 같은 수 중 XX와 서로소인 수 하나를 골라 XX를 그 수로 바꾼다.
  • 더 이상 XX의 값을 바꿀 수 없는 사람이 진다.

혁준이의 선공으로 게임이 진행된다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

입력

첫 번째 줄에 처음 화면에 표시되는 두 양의 정수 XX, YY가 공백으로 구분되어 주어진다. (2≤X<Y≤1,000)(2 \le X < Y \le 1\\,000)

출력

혁준이가 이긴다면 khj20006을, 익준이가 이긴다면 putdata를 출력한다.

예제3

  1. 예제 1

    입력
    2 6
    
    예상 출력
    putdata
    
  2. 예제 2

    입력
    3 9
    
    예상 출력
    putdata
    
  3. 예제 3

    입력
    11 12
    
    예상 출력
    khj20006