Codeforces #670 Div2 E. Deleting Numbers

また変わった問題設定だな。
https://codeforces.com/contest/1406/problem/E

問題

整数Nが指定されるので、[1,N]の範囲にある整数Xを当てるinteractive問題。
初期状態でS={1,2,...,N}である。
ここに対し、以下のクエリを10000回以内でXを当てよ。

• 整数Aを指定し、SのうちAの倍数の個数を答える。
• 2以上の整数Aを指定し、SのうちAの倍数の個数を答える。その後、SからAの倍数を取り除く。ただしXはAの倍数であっても取り除かれない。

解法

まず、Xのうち√N以下の素因数を明らかにしよう。
√N未満の素数pに対し、p,p^2,p^3....で後者のクエリ→前者のクエリと実行することで、Xがその素因数の何乗を約数に持つかを確定できる。

以後、Xに対し√Nより大きな素因数を探る。
その場合、チェックしていない素因数のうち大きな順にいくつか後者のクエリを適用し、その後前者のクエリを適用することで、各素因数を含むか判定していこう。

int N;
int X;
const int prime_max = 100000;
vector<int> prime;
int NP,divp[prime_max];
int alive[101010];
int ask;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int opA(ll v) {
	int i,num=0;
	ask++;
	cout<<"A "<<v<<endl;
	if(X) {
		for(i=v;i<=N;i+=v) num+=alive[i];
	}
	else {
		cin>>num;
	}
	return num;
}

int opB(ll v) {
	int i,num=0;
	ask++;
	cout<<"B "<<v<<endl;
	if(X) {
		for(i=v;i<=N;i+=v) {
			num+=alive[i];
			if(i!=X) alive[i]=0;
		}
	}
	else {
		cin>>num;
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) alive[i]=1;
	cprime();
	
	ll cur=1;
	vector<int> cand;
	int did=0;
	FOR(i,NP) {
		
		if(prime[i]>N) {
			break;
		}
		if(1LL*prime[i]*prime[i]>N) {
			cand.push_back(prime[i]);
			continue;
		}
		
		did++;
		opB(prime[i]);
		while(cur*prime[i]<=N) {
			x=opA(cur*prime[i]);
			if(x==0) break;
			cur*=prime[i];
		}
	}
	
	
	while(cand.size()) {
		int step=min(100,(int)cand.size());
		int num=opA(1);
		FOR(i,step) {
			num-=opB(cand[cand.size()-1-i]);
		}
		int num2=opA(1);
		if(num2!=num) {
			FOR(i,step) if(opA(cand[cand.size()-1-i])) cur*=cand[cand.size()-1-i];
		}
		cand.resize(cand.size()-step);
		
	}
	
	cout<<"C "<<cur<<endl;
	cerr<<ask<<endl;
	
}

まとめ

色々考えつくなぁ。