Hidden Number

연산 전후의 수열 원소 합의 홀짝성을 비교하자.

선택한 두 수가 $a,b$일 때, 두 수를 제거하고 $|a-b|$를 추가한다. 홀짝성에 대해

$$|a-b|\equiv a-b\equiv a+b\pmod 2$$

이므로 수열 전체 원소 합의 홀짝성은 변하지 않는다.

초기 수열은 $(1,2,\cdots,2x)$이므로 원소 합은

$$1+2+\cdots+2x=x(2x+1)$$

이다. $2x+1$은 홀수이므로

$$x(2x+1)\equiv x\pmod 2$$

가 성립한다. 따라서 마지막으로 남은 원소의 홀짝성도 $x$의 홀짝성과 같다.

즉, $f(x)\equiv x\pmod 2$이다. 그러므로 $P_i\equiv r_i\pmod 2$에서

$$K_i=1-P_i$$

를 얻는다.

비트열 $K$를 정수로 만든 뒤,

$$N=C\oplus K$$

를 계산하면 된다.

Solution written by GPT5.5