题目描述

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.

题目大意

有如下的一个程序来计算 $a^d(mod \ n)$，（$d,n$是常数）

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;
 	}
}

其中，计算 $x * y\ \ mod \ n$ （上述伪代码中的第 $5$ 行和第 $7$ 行）需要消耗 $(bits(x) + 1)* (bits(y) + 1)$ 纳秒，$bits(x)$ 是 $x$ 的二进制表示中不带前导零的位数，更正式的说，为 $\lceil \log_2(x+1) \rceil$，其他指令可以认为不需要任何时间。

你知道 $n$ ，但不知道 $d$， 你可以通过不超过 $30000$ 次询问对于 $a$ 计算 $a^d(mod \ n)$ 所用纳秒数。

正式数据中，$n,d$ 的生成方式如下：随机挑选两个 $[2^{29},2^{30}-1]$ 的质数 $p,q$，$n=pq$，而 $d$ 为在 $[1,\varphi(n)]$ 随机挑选的，与 $\varphi(n)=(p-1)*(q-1)$ 互质的数

这是一道交互题

首先，将给出整数 $n$

有两种指令可用：

“? a”询问对于正整数 $a$ 计算 $a^d(mod \ n)$ 所用纳秒数。要求$a<n$。返回所用的纳秒数

“! d”表示确定了 $d$ 的值并提交，你的程序应当在此后结束。

15
980
293

? 3
? 8
! 5