[Codeforces 679A] Bear And Prime 100 交互题

The hidden number in the first query is 30. In a table below you can see a better form of the provided example of the communication process.

The hidden number is divisible by both 2 and 5. Thus, it must be composite. Note that it isn't necessary to know the exact value of the hidden number. In this test, the hidden number is 30.

59 is a divisor of the hidden number. In the interval [2, 100] there is only one number with this divisor. The hidden number must be 59, which is prime. Note that the answer is known even after the second query and you could print it then and terminate. Though, it isn't forbidden to ask unnecessary queries (unless you exceed the limit of 20 queries).

大致题意：系统生成一个[2,100]的数字，每次询问一个数是否是这个数的约数，20次询问判断这个数字是质数还是合数.

题解： 一个[2,100]区间内的数字要么是质数，要么是合数，并不会出现其他情况，

           所以，这道题只要对合数进行判定即可求解。

           考虑一个合数的表现形式，如果k是一个合数，p代表质数，

           第一种情况，k只有1个质因子，此时存在p使得p和p^2都是k的约数，从而对于p=2,3,5,7进行8次询问即可；

           否则，k有两个及以上质因子，显然p<=50，对于[2,50]内的所有质数进行询问，判断是否有2个数同时为k的质因子即可，

           [2,50]范围内总共有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47共15个质数，其中2,3,5,7已经在第一种情况中询问过了，还需要11次询问；

           这样，就可以在11+8=19次询问以内得到k是否是一个质数了.

Code：

#include <bits/stdc++.h>
using namespace std;
int ask[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
bool res[19];
int main (){
	char s[5];int i,j,cnt=0;
	for (i=0;i<19;i++)
	{printf ("%d\n",ask[i]);
	fflush(stdout);scanf ("%s",s);
	if (s[0]=='y') {res[i]=1;}
	else {res[i]=0;}
	}
	for (i=0;i<4;i++)
	{if (res[i]&&res[i+15])
	{puts("composite\n");exit(0);}
	}
	for (i=0;i<15;i++)
	{if (res[i]) {cnt++;}
	}
	if (cnt>=2) {puts("composite");}
	else {puts("prime");}
	return 0;
}