注意到问 \(x\) 在 \(b\) 进制下的数位和是可以得到 \(x\bmod (b-1)\) 的，所以我们相当于可以指定一个 \(d\)，然后得到 \(x\bmod d\)。
一个想法是记录当前状态 \((l,r,A)\)，表示当前确定范围 \([l,r]\)，已知答案 \(\bmod A\) 的值，然后转移直接向下搜决策。但是这样状态数有点过于大，加一点减枝可以搜出 \(3\) 次问 \(1\sim 5\times 10^4\) 的方案，足够通过 E1。
观察到我们用两次只能区分 \(1\sim 9\)，但是 \(10\sim 2\times 10^9\) 怎么看也不太能两次问出来。考虑到原来的交互是得出数位和，这是比余数更强的。写一个暴力可以发现，我们可以用两次交互区分出 \(1\sim 32\)，那么现在就是要两次问出询问范围 \(33\sim 2\times 10^9\)，而且现在已知了答案 \(\bmod 32\) 的值，事实上这个就可以直接搜出一组方案。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int inf = 1e9;ll Ask(ll x) {cout << "? " << x << endl;ll res;cin >> res;return res;
}ll AskMod(ll m) { // return -1 if <= mreturn Ask(m + 1) % m;
}const int kL = 1e6 + 5;
int pc;
int pri[kL];
bool ispr[kL];void Sieve(int V = kL - 3) {fill_n(ispr, V + 3, 1);ispr[0] = ispr[1] = 0;for(int i = 2; i <= V; i++) {if(!ispr[i]) continue;pri[++pc] = i;for(int j = i + i; j <= V; j += i) {ispr[j] = 0;}}
}map<array<ll, 4>, int> mp, num;int DFS(int dep, int l, int r, ll A) {// cout << "dfs: " << dep << " " << l << " " << r << " " << A << "\n";array<ll, 4> k {dep, l, r, A};if(r - l + 1 <= A) return dep;if(dep == 2) return inf;if(mp.count(k)) return mp[k];vector<int> vec;int len = r - l + 1;if(r - l + 1 <= 100) {for(int i = l; i <= r; i++) {vec.push_back(i);}}else {// for(int i = l; i <= r; i++) {// if(__gcd<ll> (A, i) == 1) {// vec.push_back(i);// }// }for(int i = 2; i <= 20; i++) {int v = l + (len >> i) - 1;int p = lower_bound(pri + 1, pri + pc + 1, v) - pri;for(int j = max(p - 100, 1); j <= min(p + 100, pc); j++) {if(pri[j] <= r) {vec.push_back(pri[j]);}}}}sort(vec.begin(), vec.end());vec.erase(unique(vec.begin(), vec.end()), vec.end());int res = inf, chs = 0;for(int i : vec) {int lft = DFS(dep + 1, l, i, A);if(lft >= res) continue;int val = max(lft, DFS(dep + 1, i + 1, r, A / __gcd<ll> (A, i) * i));if(res > val) res = val, chs = i;}return num[k] = chs, mp[k] = res;
}int S(int x, int m) {if(x < m) return -1;int s = 0;while(x) s += x % m, x /= m;return s;
}void Solve() {int tmp = AskMod(32);int qwq;if(tmp == -1) {int ttt = Ask(4);if(ttt != -1) {int get = Ask(8);for(int i = 4; i <= 32; i++) {if((S(i, 8) == get) && (S(i, 4) == ttt)) {cout << "! " << i << endl;cin >> qwq;return ;}}}else {int get = Ask(2);for(int i = 1; i <= 3; i++) {if(S(i, 2) == get) {cout << "! " << i << endl;cin >> qwq;return ;}}}}else {int l = 33, r = 2e9, A = 32, B = tmp;for(int d = 0; d <= 1; d++) {int v = num[array<ll, 4> {d, l, r, A}];int rem = AskMod(v);if(rem == -1) {r = v;}else {l = v + 1;while(B % v != rem) B += A;A = A / __gcd(A, v) * v;}}while(B < l) B += A;cout << "! " << B << endl;cin >> qwq;}
}int main() {// freopen("1.in", "r", stdin);// freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);Sieve();DFS(0, 33, 2000000000, 32);// int L, R, C;// cin >> L >> R >> C;// cout << DFS(0, L, R, C) << "\n";// for(int R = L; ; R++) {// cerr << R << endl;// if(DFS(0, L, R, 1) == inf) {// cout << R - 1 << "\n";// return 0;// }// }// cerr << mp.size() << endl;int t;ll k, c;cin >> t >> k >> c;while(t--) Solve();return 0;
}