곱셈

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

요약

짝수 n이 주어지면 n개의 서로 다른 수를 출력합니다. 숨겨진 홀수 x를 곱한 뒤 2^31로 나눈 나머지 중 절반을 돌려받아 x를 맞혀야 합니다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 비트 연산, 확률
정답자: 아직 제출이 없습니다

문제

이 문제는 상호작용 문제이다. 심사위원은 $1$ 이상 $2^{31}-1$ 이하의 비밀스러운 홀수 $x$ 를 골랐다. 당신의 과제는 이 값을 맞히는 것이다.

심사위원이 짝수 $n$ 을 준다. 당신은 $0$ 이상 $2^{31}-1$ 이하의 서로 다른 정수를 정확히 $n$ 개 출력해야 한다. 심사위원은 각 수에 $x$ 를 곱하고, 그 결과를 $2^{31}$ 으로 나눈 나머지를 구한다. 이어서 이 곱셈 결과 중 크기가 $n/2$ 인 부분집합을 모든 부분집합이 같은 확률로 나오도록 무작위로 고른다. 고른 값들은 순서를 섞어 당신에게 돌려준다. 그 다음 당신은 $x$ 의 올바른 값을 출력한다.

각 테스트에서 $x$ 는 미리 정해져 있으며 바뀌지 않는다.

예제1

예제 1
입력
```
4

9 6
```
예상 출력
```
1 2 3 4

3
```