뉴트리노 레이더

얼마 전 천문학자들이 행성이 $N$개인 별 $\zeta$-2019A를 발견했다. 이제 그중 한 행성이 생명체가 살 만한 환경이라는 사실이 밝혀졌다. 그러나 이 별은 너무 멀리 있어서, 행성을 조사하려면 강력한 뉴트리노 레이더가 필요하다.

레이더는 다음과 같이 동작한다. 먼저 레이더가 별계 방향으로 뉴트리노 흐름을 보낸다. 이 흐름은 정수 매개변수 $X$와 $Y$로 정해진다. 별계에서 반사되어 돌아온 신호를 분석하면 정수 $B = \gcd(X, A + Y)$를 얻을 수 있다. 여기서 $A$는 생명체가 살 만한 행성의 번호이고(행성은 $\zeta$-2019A에서 가까운 순서대로 $1 \ldots N$번까지 매겨져 있다), $\gcd(X, Y)$는 $X$와 $Y$의 최대공약수, 즉 둘 다 나누어 떨어지는 가장 큰 정수를 뜻한다. 뉴트리노 흐름을 보내는 데는 에너지가 많이 들기 때문에 최대 40번까지 보낼 수 있다.

이제 천문학자들에게는 레이더를 제어하고 생명체가 살 만한 행성의 번호를 알아내는 프로그램이 필요하다. 프로그램의 핵심은 int Locate(int n) 함수다. 이 함수는 한 번 호출되며, 인자로 별 $\zeta$-2019A의 행성 수 $N$을 받는다. 함수는 생명체가 살 만한 행성의 번호 $A$($1 \le A \le N$)를 반환해야 한다.

Locate 함수는 작업 중에 int Scan(int x, int y) 함수를 사용할 수 있다. Scan은 매개변수 $X$와 $Y$($1 \le X \le 10^9$, $0 \le Y \le 10^9$)로 레이더를 작동시키고, 신호 분석 결과인 $B = \gcd(X, A + Y)$를 반환한다. Scan은 최대 40번까지 사용할 수 있다.

테스트 환경에는 필요한 함수가 이미 정의된 예제 파일이 주어지며, 여러분은 Locate 함수의 구현만 추가하면 된다. 해답 파일에 직접 만든 함수를 추가해도 된다. 자신의 컴퓨터에서 해답을 테스트할 수 있도록 채점 프로그램 예제도 제공된다. 서버에서는 반환된 답이 맞는지도 확인하는 다른 채점 프로그램을 사용한다. 자신의 컴퓨터에서 컴파일하고 테스트하려면:

한 줄에 정수 두 개가 주어진다. 첫 번째는 별 $\zeta$-2019A의 행성 총수 $N$($1 \le N \le 10^9$)이고, 두 번째는 생명체가 살 만한 행성의 번호 $A$($1 \le A \le N$)다.

출력 파일에는 채점 프로그램과 Locate 함수가 주고받은 상호작용 기록이 쓰여 있다.