CF1406E 【Deleting Numbers】

蒟蒻语

蒟蒻这次 \(CF\) 又双叒叕掉分了，\(C\) 都没有调出来。

还好再最后 \(10\) 秒钟调了下 \(E\) 块长 (块长 \(100\) => \(98\)),才没有掉得那么惨。

蒟蒻解

\(100000\) 里总共有 \(9592\) 个质数。

(下文 \(p_i\) 表示第 \(i\) 个质数)

首先 \(x\) 大于 \(\sqrt n\) 的质因数最多一个。

对于大于 \(\sqrt n\) 的质数数可以进行分块, 块长为 \(B\)。

每次把一个块里面的质数删完(B p[i]), 然后删完之后看看删掉的数的总数是否等于 A 1 答案的变化量。如果不相等，那么说明 \(x\) 一定有一个质因数处于这个块内，暴力 A p[i] 判断是否为 \(1\) 就行了。如果 A p[i] 为 \(1\), 那么就说明 \(x\) 大与 \(\sqrt n\) 的质因数就是 \(p_i\)。

那么小于 \(\sqrt n\) 的质数就很好弄了，直接先删这个质数的倍数，然后一个个暴力判 \(x\) 最多能整除该质数的几次方就好了。

蒟蒻码

不懂的看丑陋无比的代码吧

#include<bits/stdc++.h>

#define N 100010

#define B 98

using namespace std;

int Ans = 1;

bool Prime[N];

int tot, p[N];

void xxs(int x) {

	for(int i = 2; i <= x; i++) {

		if(!Prime[i]) p[++tot] = i;

		for(int j = 1; p[j] * i <= x && j <= tot; j++) {

			Prime[p[j] * i] = 1;

			if(i % p[j] == 0) break;

		}

	}

}

int n, tt, maxn;

void get(int x) {

	int now = 1;

	printf("B %d\n", x);

	fflush(stdout);

	scanf("%d", &tt);

	while(1) {

		now *= x;

		if(now > n) break;

		printf("A %d\n", now);

		fflush(stdout);

		scanf("%d", &tt);

		if(tt == 0) break;

		Ans *= x;

	}

}

int main() {

	scanf("%d", &n);

	xxs(n);

	for(int i = 1; i <= tot; i++) if(p[i] <= sqrt(n)) maxn = i;

	int ssss = n, L = maxn, R = tot;

	for(int i = 1; i <= B; i++) {

		int L = (i - 1) * B + 1, R = min(i * B, tot);

		for(int j = L; j <= R; j++) {

			if(j <= maxn) continue;

			printf("B %d\n", p[j]);

			fflush(stdout);

			scanf("%d", &tt);

			ssss -= tt;

		}

		printf("A 1\n");

		fflush(stdout);

		scanf("%d", &tt);

		if(ssss != tt) {

			for(int j = L; j <= R; j++) {

				if(j <= maxn) continue;

				printf("A %d\n", p[j]);

				fflush(stdout);

				scanf("%d", &tt);

				if(tt) {

					Ans = p[j];

					break;

				}

			}

			break;

		}

		if(R == tot) break;

	}

	for(int i = 1; i <= maxn; i++) get(p[i]);

	printf("C %d\n", Ans);

	fflush(stdout);

	return 0;

}

巴特西

CF1406E 【Deleting Numbers】

蒟蒻语

蒟蒻解

蒟蒻码

最新文章

热门文章