Informatica Online Judge

  양초 고르기 [2378 / 094A]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1   Total Tried : 5


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[36th 최정현(gs18117)]
Writer ID : [gs18117]

Background

어둠의 존재는 주변이 나타나는 몹으로 코볼트들이 굉장히 무서워하는 몹이고 이 몹을 피하기 위해 코볼트들은 양초에 매우 집착한다.

그래서 코볼트들의 왕 토그왜글은 자신의 보물(보물은 사실 엄청 큰 양초다)을 다른 코볼트들이 훔쳐가지 못하도록 아주 기묘한 방법을 생각해냈다.

동굴이 총 N개가 있고 이 중에 진짜 양초는 하나의 동굴의 끝에 있다. 나머지 양초들은 불량으로, N개의 동굴들 중 하나에 들어갈 경우 가는 도중에 양초가 꺼져서 어둠의 존재한테 죽게된다.

토그왜글은 진짜 양초가 있는 방을 랜덤하기 위해 다음과 같은 규칙을 고안해냈다. K번째 동굴에 불량 양초를 하나씩 넣고, 나머지 빈 동굴들 중 k번째에 다시 양초를 하나 넣고 이 과정을 (N-1)번 한다.(N번 동굴 다음에는 1번 동굴)

이후 마지막 빈 동굴에 진짜 양초를 넣는다. 몰론 K번째 동굴까지 계속 세는 것은 귀찮은 일이므로 토그왜글은 (N-1)*K이 10^12이하의 숫자가 되도록 설정하였다. 문제는 며칠 뒤 토그왜글이 어느 동굴에 진짜 양초가 있는지 까먹었다는 것이다.

그리하여 토그왜글은 모험가인 당신에게 N과 K를 알려주고 진짜 양초가 있는 동굴을 빨리 찾아주면 금을 주겠다고 했다. 양초가 있는 동굴을 찾자!

Input

첫째 줄에 정수 N과 K가 주어진다.((N-1)*K<= 10^12 )

Output

동굴의 번호를 출력한다.

IO Example

입력
7 3

출력
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]