두 더미 위의 게임

두 명의 플레이어가 다음 게임을 한다.

두 사람은 공이 들어 있는 비어 있지 않은 두 더미 앞에 앉아 있다. 설명을 위해 두 더미 중 공의 개수가 더 적거나 같은 쪽을 A라 하고, 다른 쪽을 B라 하자. 즉 A ≤ B이다. 시작 비율 A : B = α는 해당 게임이 진행되는 동안 중요하며, 더미 속 공의 개수가 어떻게 바뀌든 그대로 유지된다. 플레이어는 번갈아 움직이며, 적어도 하나의 더미에서 적어도 하나의 공을 가져간다. 움직일 수 없거나 잘못된 움직임을 한 플레이어가 진다. 따라서 마지막으로 올바른 움직임을 둔 플레이어가 이긴다.

한 더미에서 가져간 공의 개수를 x, 다른 더미에서 가져간 공의 개수를 y라 하자. 여기서 x는 둘 중 더 적거나 같은 쪽의 개수로 둔다. 그러면 올바른 움직임의 규칙을 다음과 같이 세울 수 있다.

• 움직임은 x : y ≠ α일 때만 올바르다. 단, 0 ≤ x ≤ y이고 y > 0이다.
• 당연히 더미에 남아 있는 공보다 많은 공을 그 더미에서 가져갈 수는 없다.

예로 A=12, B=18인 경우를 보자. 이 게임에서 잘못된 가져간 공의 비율은 x:y = α = 12:18 = 2:3이다. 그 밖의 모든 가져간 공의 비율은 올바르다. 다음은 첫 번째 플레이어에게 잘못된, 따라서 지게 되는 움직임의 예이다.

1. 모든 공을 가져가는 경우, 즉 x=12, y=18. 이 움직임은 x:y = 12:18 = 2:3 = α이므로 명백히 잘못이다.
2. 더미 A에서 공 3개를 가져가 9개를 남기고, 더미 B에서 공 2개를 가져가 16개를 남기는 경우. x=2, y=3이고 x:y = 2:3 = α이므로 잘못된 움직임이다. 주의! 이런 움직임 뒤에 더미 속 공의 비율은 9:16이 되지만, 이는 고정된 비율 α를 바꾸지 않는다. α는 이 게임이 시작되기 전에 정해진 대로 2:3으로 그대로 유지된다.
3. A에서 8개, B에서 12개를 가져가는 경우, 즉 x=8, y=12, x:y=8:12=2:3. 이 움직임 뒤에 A의 공은 4개, B의 공은 6개가 된다. (이 움직임 뒤 더미 속 공의 비율은 바뀌지 않는다. 4:6=2:3. 그러나 다시 강조하지만, 움직임은 이 게임에서 중요한 비율 α에 영향을 주지 않는다. α는 첫 움직임 전에 정해지고 게임이 끝날 때까지 일정하게 유지된다.)

첫 번째 플레이어에게 가능한 올바른 움직임은 많이 있다. 어느 더미에서든 공 1개를 가져가는 것(0:1 = 0 ≠ α), 더미 하나를 통째로 가져가는 것(예를 들어 두 번째 더미, 0:18 = 0 ≠ α), 각 더미에서 최대 개수인 12개를 가져가는 것(12:12 = 1 ≠ α), A에서 10개, B에서 5개를 가져가는 것(5:10 = 1:2 ≠ α) 등이다. 물론 더미에 남아 있는 공보다 많은 공을 가져가려 하면 잘못이다. 그리고 적어도 하나의 더미에서 적어도 하나의 공을 가져가야 한다는 점을 잊지 말자. x = y = 0인 “움직임”(즉, “상황을 그대로 둔다.”)은 잘못이며 따라서 지게 된다.

프로그램 arelgame을 작성해, 첫 번째 플레이어가 이기는 첫 움직임의 개수를 계산하라. 상대가 아무리 좋은 또는 나쁜 움직임을 두더라도 성공으로 이끄는 움직임을 “이기는” 움직임이라 한다.

표준 입력에서 한 줄을 읽으며, 이 줄에는 공백으로 구분된 두 양의 정수만 들어 있다. 각각 첫 번째 더미와 두 번째 더미의 공 개수이다.

프로그램은 표준 출력에 한 줄을 보내야 하며, 이 줄에는 음이 아닌 정수 하나만 들어 있다. 첫 번째 플레이어가 이기는 첫 움직임의 개수이다.

각 더미의 공 개수는 10^18을 넘지 않는다.