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