CF1406E Deleting Numbers 题解

题意：

这是一道交互题。

已知 $n$, 有一个未知数 $x$ $(1\le x\le n)$，你需要求出 $x$ 的值。

一开始，你有一个集合 $S=\{x\mid x\le n,x\in \mathbb{N^+}\}$

你可以对这个集合执行不超过 $10000$ 次 A、B、C 操作（总和不超过）。

A $a$，表示求出 $S$ 中 $a$ 的倍数的个数 $(1\le a\le n)$

B $a$，表示求出 $S$ 中 $a$ 的倍数的个数，

并将这些 $a$ 的倍数从 $S$ 中删去（$x$ 是不会被删掉的） $(2\le a\le n)$

C $a$，表示你知道了 $x=a$ $(1\le a\le n)$

所有的 $a$ 均为整数。数据范围 $1 \le n \le 10^5$ 。

由于本题和整除有关，所以很容易想到特殊考虑质因子。

假设我们知道 $x$ 的所有质因子，那么可以通过枚举幂次，然后反复询问 $\mathrm{A}\ p^k$ 以得到答案。

现在考虑对于一个质数 $p$ 询问一次 $\mathrm{B}\ p$ ，同时我们也维护一个集合，表示会删除 $x$ 时，还剩哪些数

若得到的答案和我们维护得到的答案不同，则说明 $x$ 有 $p$ 这个质因子，暴力询问幂次即可。

通过这样的方法，我们可以找到除了最小质因子以外的全部质因子（因为最小质因子得到的答案是相同的）

考虑分块来找到这个最小质因子。记 $m = \pi(n)$ ，即质数的个数。

每隔 $\sqrt{m}$ 个质数做一次 $\mathrm{A}\ 1$ 询问，检查最小质因子是否在当前块内。

如果在，则暴力扫描块内的每个质数 $p$ ，每次询问 $\mathrm{A}\ p$ ，即可得到最小质因子，进而确定 $x$ 。

时间复杂度 $\mathcal{O}(n \log n)$ ，总操作次数为 $m + 2\sqrt{m} + \log n$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

char ck[N], vis[N]; int pcnt, p[N];
void init(int n)
{
    rep(i, 2, n)
    {
        if(!ck[i]) { p[++pcnt] = i; }
        rep(j, 1, pcnt)
        {
            if(i * p[j] > n) break;
            ck[i * p[j]] = true; if(i % p[j] == 0) break;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, x; cin >> n; init(n);
    int m = sqrt(pcnt), tot = n, ans = 1; bool ok = false;
    rep(i, 1, pcnt)
    {
        if(i >= m && ans * p[i - m + 1] > n) break;
        cout << "B " << p[i] << endl;
        int cnt = 0;
        for(int j = p[i]; j <= n; j += p[i])
            if(!vis[j]) { ++cnt, --tot; vis[j] = true; }
        cin >> x;
        if(x != cnt)
        {
            for(int k = p[i]; k <= n; k *= p[i])
            {
                cout << "A " << k << endl; cin >> x;
                if(x) ans *= p[i]; else break;
            }
        }
        if((i == pcnt || i % m == 0) && !ok)
        {
            cout << "A 1" << endl; cin >> x;
            if(x != tot)
            {
                rep(j, i - m + 1, i)
                {
                    for(int k = p[j]; k <= n; k *= p[j])
                    {
                        cout << "A " << k << endl; cin >> x;
                        if(x) { ans *= p[j], ok = true; } else break;
                    }
                    if(ok) break;
                }
            }
        }
    }
    cout << "C " << ans << endl;
    return 0;
}