考虑询问每个质因子及其次数最后组合得到 \(n\)。
注意到 \(n\) 最多只会有 \(1\) 个 \(> \sqrt{n}\) 的质因子。
于是考虑分成 \(\le \sqrt{n}\) 和 \(> \sqrt{n}\) 来考虑。
对于 \(\le \sqrt{n}\) 的 \(p\)。
考虑先 \(\texttt{B}\ p\)，那么还剩下的 \(p\) 的倍数就只有 \(x\) 了。
接下来询问 \(\texttt{A}\ p\)，如果为 \(1\) 说明 \(p | x\)。
继续询问 \(\texttt{A}\ p^2\)，如果为 \(1\) 说明 \(p^2 | x\)。
以此类推。
这部分不会超过 \(147\) 步。
这部分操作完后，剩下的数就只有 \(1\)，\(x\) 和 \(> \sqrt{n}\) 的质数了，\(> \sqrt{n}\) 的质数有 \(9527\) 个。
如果 \(x\) 有 \(\le \sqrt{n}\) 的质数，那么在询问 \(x\) 的 \(> \sqrt{n}\) 的质因子时会得到 \(2\)，就可以判出。
否则 \(x\) 如果是 \(> \sqrt{n}\) 的质数，考虑分块。
按 \(\lfloor\sqrt{9527}\rfloor=97\) 为块长分块，一次性把块内的质数都删掉，如果说查询 \(\texttt{A}\ 1\) 得到的值对比上次得到的值的差值与当前块块长不一样，就说明 \(x\) 在这个块内。
因为如果 \(x\) 不在这个块内每个质数都会被删掉减少的值就为块长，只有在块内时会使得一个质数不会被删掉就不同。
那么找到其块后就可以暴力询问块内的每个数了。
最坏情况下查询次数 \(147 + 9527 + 97 + \lceil\frac{9527}{97}\rceil = 9870\) 次。
代码
#include<bits/stdc++.h>
const int maxn = 1e5 + 10;
bool vis[maxn], ud[maxn];
int pr[maxn], m;
int main() {
int n; std::cin >> n;
for (int i = 2; i <= n; i++)
if (! vis[i]) {
pr[++m] = i;
for (int j = i; j <= n; j += i) vis[j] = 1;
}
auto qry = [&](char c, int x) {std::cout << c << ' ' << x << std::endl;};
auto get = [&]() {int x; std::cin >> x; return x;};
int x = 1;
for (int i = 1; i <= m; i++)
if (1ll * pr[i] * pr[i] <= n) {
qry('B', pr[i]), get();
for (int j = pr[i]; ; j *= pr[i]) {
qry('A', j);
if (! get()) break;
x *= pr[i];
if (1ll * j * pr[i] > n) break;
}
}
std::vector<int> P;
qry('A', 1);
int cnt = get(), B = sqrt(cnt);
auto solve = [&]() {
qry('A', 1);
if (get() != cnt) {
for (int v : P) {
qry('A', v);
if (get() == 1) {
x *= v;
break;
}
}
return true;
}
P.clear();
return false;
};
bool f = 0;
for (int i = 1; i <= m; i++)
if (1ll * pr[i] * pr[i] > n) {
cnt--;
qry('B', pr[i]);
if (get() == 2) {
x *= pr[i];
f = 1;
break;
}
P.push_back(pr[i]);
if (P.size() == B)
if (solve()) {f = 1; break;}
}
! f && (solve(), 1);
qry('C', x);
return 0;
}