[思维]GCD Guess Codeforces1665D

This is an interactive problem.

There is a positive integer 1≤x≤1091≤x≤109 that you have to guess.

In one query you can choose two positive integers a≠ba≠b. As an answer to this query you will get gcd(x+a,x+b)gcd(x+a,x+b), where gcd(n,m)gcd(n,m) is the of the numbers nn and mm.

To guess one hidden number xx you are allowed to make no more than 3030 queries.

Input

The first line of input contains a single integer tt (1≤t≤10001≤t≤1000) denoting the number of test cases.

The integer xx that you have to guess satisfies the constraints: (1≤x≤1091≤x≤109).

Interaction

The hidden number xx is fixed before the start of the interaction and does not depend on your queries.

To guess each xx you can make no more than 3030 queries in the following way:

"? a b" (1≤a,b≤2⋅1091≤a,b≤2⋅109, a≠ba≠b).

For this query you will get gcd(x+a,x+b)gcd(x+a,x+b).

When you know xx, print a single line in the following format.

"! x" (1≤x≤1091≤x≤109).

After that continue to solve the next test case.

If you ask more than 3030 queries for one xx or make an invalid query, the interactor will terminate immediately and your program will receive verdict Wrong Answer.

After printing each query do not forget to output end of line and flush the output buffer. Otherwise, you will get the Idleness limit exceeded verdict. To do flush use:

fflush(stdout) or cout.flush() in C++; System.out.flush() in Java; flush(output) in Pascal; stdout.flush() in Python; Read documentation for other languages.

Hacks

To use hacks, use the following format of tests:

The first line should contain a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first and only line of each test case should contain a single integer xx (1≤x≤1091≤x≤109) denoting the integer xx that should be guessed.

Example

input

2

1

8

1

output

? 1 2

? 12 4

! 4
? 2000000000 1999999999

! 1000000000

题意： 这是一道交互题，有一个被隐藏的数字x，现在需要通过不超过30次的询问找出它。每次询问需要给出不相等的两个数a和b，然后系统会返回gcd(x+a, x+b)给你。

分析： 按位考虑，首先看最低位，令a = 1, b = 3，此时如果最低位是0，那么x+a和x+b都应该是奇数，而奇数和奇数的gcd一定也是奇数，如果最低位是1，那么x+a和x+b都应该是偶数，偶数和偶数的gcd一定也是偶数。根据这点就可以求出最低位是否为1，将这个方法扩展至判断第i位，只需要构造a、b让x+a和x+b后i-1位全为0且第i位的结果是x的第i位+1，如果x的第i位为1，那么x+a和x+b的后i位都是0，也就是说x+a和x+b的gcd是2^(i+1)的倍数，如果x的第i位为0，那么x+a和x+b的第i位为1，后i-1位都是0，这说明x+a和x+b的gcd一定不是2^(i+1)的倍数。用这种方法对每一位分别判断就能够得到最终x的数值了。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#define int long long
using namespace std;

int ans[35];

signed main()
{
	int T;
	cin >> T;
	while(T--){
		for(int i = 0; i <= 29; i++) ans[i] = -1;
		for(int i = 0; i <= 29; i++){
			int a, b = 1<<i;
			int num = 0;
			for(int j = 0; j < i; j++)
				num += ans[j]<<j;
			a = b-num;
//			a += b<<1;
			b = a + (1 << (i + 1));
			printf("? %lld %lld
", a, b);
			fflush(stdout);
			int gcd;
			scanf("%lld", &gcd);
			if(gcd%(1<<(i+1)) == 0) ans[i] = 1;
			else ans[i] = 0;
		}
		int num = 0;
		for(int i = 0; i <= 29 && ans[i] != -1; i++)
			num += ans[i]<<i;
		printf("! %lld
", num);
		fflush(stdout);
	}
	return 0;
}