题目描述

Heidi is analyzing a peculiar device. This device takes an a as input and computes $a^d(mod n)$ using thefollowing pseudocode and some integers $d$ and $n$ stored in this device:

modPow(a, d, n) {
 r = 1;
 for (i = 0; i < 60; ++i) {
   if ((d & (1 << i)) != 0) {
     r = r * a % n;
   }
 a = a * a % n;
 }
}

Note that the pseudocode assumes arbitrary sized integers, $<<$ denotes bitwise shift left, & denotes bitwise

and, and % denotes modulo.

The device does not tell Heidi the result of the computation. However, Heidi can measure how long does the computation take. She knows that only multiplication modulo $n$ (lines $5$ and $7$ in the above pseudocode) takes any measurable amount of time, all other lines can be assumed to take $0$ nanoseconds.

Moreover, she knows that it takes $(bits(x) + 1) · (bits(y) + 1)$ nanoseconds to multiply $x$ by $y$ modulo $n$ , where $bits(x)$ is the number of bits in the binary representation of $x$ without leading zeros, or more formally $\text{bits(x)} = ⌈\log_2 (x + 1)⌉.

Heidi knows the integer $n$ but does not know the integer $d$ . She wants to find $d$ by feeding the device different integers a as input and measuring the time the computation takes for each a .

She knows that $n$ and $d$ were chosen in the following way: first, two prime numbers $p$ and $q$ with $30$ bits in binary representation (in other words, between $229$ and $230 −1)$ were picked independently and uniformly at random. Then the number $n$ was computed as $n = p · q$ . Then the number $m = φ(n) = (p−1)·(q −1)$

was computed. Then $d$ was picked uniformly at random between $1$ and $m − 1$ inclusive, such that it is coprime with $m$ .

Interaction Protocol

First, the testing system writes the integer $n$ -- the modulo used by the device. Note that $n$ and the hidden number $d$ are guaranteed to have been generated according to the procedure described above.

Your solution shall print requests of two types:

• “? a” tells to feed a as input to the device. a must be an integer between $0$ and $n−1$ inclusive. The testing system responds with the time it took the device to compute modPow(a , d , n) in nanoseconds.

• “! d” tells the value of $d$ that your program has determined.

Don't forget to flush the output after each request!

Your solution must issue exactly one request of the second type, which must be the last request, and the solution must terminate gracefully after issuing it.

Your solution is allowed to issue at most $30 000$ requests of the first type.

Your solution will be run on $30$ testcases, working with one $(n , d)$ pair per run. For each testcase the numbers $n$ and $d$ are fixed and were generated using the procedure described above. The example below

was not generated in that manner and thus will not be used for testing your solution; it only serves to illustrate the input/output format and provide a sanity check for your calculation of the computation time.

15
980
293

? 3
? 8
! 5