Codeforces Round #670 (Div. 2) E. Deleting Numbers（交互，素数构造）

题意：
给定序列 [ 1 , n ] [1,n] [1,n],用给定的合法操作猜出 x x x
有三种操作

• A a：问含a因子的数字的个数
• B a：问含a因子的数字的个数，之后把除了答案的所有含a因子的数字从序列删除。
• C a：确定答案是a
  思路：
  交互，思路如下，明天细说，今天跑路跑路。
  
  代码：

int v[maxn], prime[maxn];//v存质数，vis判断是不是质数
int primes(int n) {
	int m = 0;
	for (int i = 2; i <= n; i++) {
		if (v[i] == 0) {//i是质数
			v[i] = i; prime[++m] = i;
		}
		for (int j = 1; j <= m; j++) {
			if (prime[j] > v[i] || prime[j] > n / i)break;
			v[i*prime[j]] = prime[j];
		}
	}
	return m;
}
int main()
{
	int n, m, ans, M, g, start;
	int t;
	int tt, tot, temp, cur;
	tot = 0;
	cur = 0;
	g = 0;
	start = 0;
	M = primes(maxn);
	ans = 1;

	//cout << M - tot << endl;
	//cout << tot << endl;*/
	sci(n);

	if (n == 1) {
		printf("C 1\n");
		return 0;
	}
	for (int i = 1; prime[i] <= n; i++) {
		//if (prime[i] == 99874/2)cout << 1 << endl;
		cur++;
		if ((LL)(prime[i]) * (LL)(prime[i]) > (LL)(n))g++;
		else start = i;
	}
	M = cur;
	//cout << (int)(sqrt(g)) << endl;
	for (int i = 1; prime[i] * prime[i] <= n; i++) {//寻找小素数(可能有多个次方)
		cur--;
		printf("B %d\n", prime[i]);
		fflush(stdout);
		sci(tt);
		printf("A %d\n", prime[i]);
		fflush(stdout);
		sci(tt);
		if (tt) {
			ans *= prime[i];
			temp = prime[i];
			while (temp*prime[i] <= n) {
				temp *= prime[i];
				//printf("B %d\n", temp);
				printf("A %d\n", temp);
				fflush(stdout);
				sci(tt);
				if (tt == 0)break;
				else ans *= prime[i];
			}
		}
	}
	int s = (int)(sqrt(g));
	int pos;
	if (ans == 1) {//只含大素数
		//lst = start + 1;
		for (int i = 0; i <= g / s - (g%s == 0); i++) {
			if (ans != 1)break;
			for (int j = 0; j < s; j++) {
				pos = start + i * s + j + 1;
				if (pos > M)continue;
				printf("B %d\n", prime[pos]);
				fflush(stdout);
				sci(tt);
				cur--;
			}
			printf("A 1\n");
			fflush(stdout);
			sci(tt);
			if (tt != cur + 1) {
				for (int j = 0; j < s; j++) {
					pos = start + i * s + j + 1;
					if (pos > M)continue;
					printf("A %d\n", prime[pos]);
					fflush(stdout);
					sci(tt);
					if (tt) {
						ans *= prime[pos];
					}
				}
			}
		}
	}
	else {//大素数，只可能一次方
		for (int i = start + 1; prime[i] <= n; i++) {
			//if (prime[i] * prime[i] <= n)continue;
			printf("A %d\n", prime[i]);
			fflush(stdout);
			sci(tt);
			if (tt == 2) {
				ans *= prime[i];
				break;
			}
		}
	}
	printf("C %d\n", ans);
	return 0;
}