CF1406E

题目

交互题，你有一个({1,...,n})的集合，你想要找出其中一个数(x)，有3个操作：

• A a：询问当前集合中有多少元素是(a)的倍数。
• B a：询问当前集合中有多少元素是(a)的倍数，然后从集合中将(a)的倍数的数全部删去，除了(x)。(x)永远不会被删除，即使它是(a)的倍数。注意这个操作要求(a>1)。
• C a：代表你找到了(x)，(x=a)。结束。

你最多可以执行操作(10000)次，(nle 100000)。

题解

很自然就想到要枚举质数去询问。(10^5)以内质数个数为(9592)。假设可以通过询问一轮知道(x)包含的质因子为(p_1,p_2,...,p_k)，那么就可以枚举质因子的幂次进行询问，得到真正的(x)，这一步最多只需要不到20次操作。

如何得到(x)包含的质因子？从小到大枚举质数进行B询问，假设当前枚举到(p_{i+1})，已经知道(x)包含(p_1,p_2,...,p_i)，那么(x)包含(p_{i+1})的条件就是操作“B (p_1p_2...p_{i+1})”返回的结果为1。这一步最多需要(9592)次操作。那么关键就是如何知道(x)包含的第一个(p_1)。

用分块的思想，每(T)次B操作后执行一次“A 1”，判断集合中剩余个数是否多1，如果是说明这段区间内的存在质数为(x)的质因子。然后遍历这段的质数挨个检查即可。当获得大于等于1个质数后，就可以用上面的方法找出剩余的质因子，故最多就只需遍历一个(T)次。这步最多需要(frac{9592}{T}+T)次操作，取(T=sqrt{9592}=98)，即最多(196)次操作。

故总的最多操作为(196+9592+20+1=9809<10000)。

#include <bits/stdc++.h>

// #define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N) 
typedef long long ll;

using namespace std;
/*-----------------------------------------------------------------*/

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f

const int N = 1e5 + 1;
const double eps = 1e-5;



bool vis[N], isnp[N];
int pri[N], cnt;
vector<int> d;
int ret = 0;

int del(int p, int n) {
	int res = 0;
	for(int i = p; i <= n; i += p) {
		if(!vis[i]) {
			res++;
			vis[i] = 1;
		}
	}
	return res;
}

int n;
int main() {
    // IOS;
	for(int i = 2; i < N; i++) {
		if(!isnp[i]) {
			pri[cnt++] = i;
		}
		for(int j = 0; j < cnt && i * pri[j] < N; j++) {
			isnp[i * pri[j]] = 1;
			if(i % pri[j] == 0) {
				break;
			}
		}
	}
	cin >> n;
	int m = 0;
	for(int i = 0; i < cnt; i++) {
		m++;
		if(pri[i] > n) {
			break;
		}
	}
	int sq = sqrt(m), pre = 0;
	ll k = 1;
	int ret = n;
	for(int i = 0; i < m && k * pri[i] <= n; i++) {
		int tnum, num;
		cout << "B " << k * pri[i] << endl;
		cin >> tnum;
		num = del(k * pri[i], n);
		ret -= num;	
		if(!d.empty()) {
			if(num != tnum) {
				d.push_back(pri[i]);
				k *= pri[i];
			}
		} else if((i - pre + 1) % sq == 0 || i == m - 1) {
			int r;
			cout << "A 1" << endl;
			cin >> r;
			if(ret != r) {
				for(int j = pre; j <= i; j++) {
					int flag;
					cout << "A " << pri[j] << endl;
					cin >> flag;
					if(flag) {
						d.push_back(pri[j]);
						k *= pri[j];
					}
				}
			}
			pre = i + 1;
		}
	}
	for(int i = 0; i < d.size() && k <= n; i++) {
		ll pw = d[i];
		while(k * pw <= n) {
			int flag;
			cout << "A " << k * pw << endl;
			cin >> flag;
			if(!flag) {
				k = k * (pw / d[i]);
				break;
			}
			pw *= d[i];
			if(k * pw > n) {
				k = k * (pw / d[i]);
				break;
			}
		}
	}
	cout << "C " << k << endl;
}