Multiplication

Time limit2sMemory limit512 MB

Summary

Given an even n, output n distinct numbers so that after multiplying by a secret odd x mod 2^31, the judge returns half of the products, and you must recover x.

Level: Hard8 of 10
Topics: Math, Number theory, Bit manipulation, Probability
Solved: No attempts yet

Problem

This is an interactive problem. The jury has chosen a secret odd number $x$ between $1$ and $2^{31}-1$ inclusive. Your task is to guess it.

The jury gives you an even number $n$ . You must output exactly $n$ distinct integers between $0$ and $2^{31}-1$ inclusive. The jury multiplies each of these numbers by $x$ and takes the result modulo $2^{31}$ . Then the jury picks a random subset of these products of size $n/2$ , with every subset equally likely, and returns it to you in random order. After that, you output the correct value of $x$ .

In each test, $x$ is fixed in advance and does not change.

Examples1

Example 1
Input
```
4

9 6
```
Expected output
```
1 2 3 4

3
```