Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：存在一个[2..100]之间的数，每次可以询问一个数是否是该数的因子，返回yes或者no，最多询问20次。每次要输出询问的数，以及最后要输出这个数是否是质数。
思路：第一次做交互题。。。发现完全不能按照以前的思路。。。
更像是相反的。。。把output看做某种输入。。。input里是某种结果。。。我要根据input里的东西来确定一些东西。
就是先有output，再有input。。。output是选手的输入（最后一个除外），input是返回结果(不是你写的代码的返回结果）
对于这道题。。我们要尽可能少得猜一个数的因子，以确定该数是否为质数。
一个数不是质数的话，就有至少两个大于1的因子。。。
很容易想到。。。判素因子。。。
由于至少有2个非1的因子才不是素数。。。最小为2，因此另一个因子不会大于50.。。
此外。。。有可能有两个相同质因数组成的因子。。。。
因此还要判一下22,35,55,77
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :Sun 02 Oct 2016 08:22:44 PM CST
4File Name :code/cf/problem/679A.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31int prime[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
32string st;
33int main()
34{
35 #ifndef ONLINE_JUDGE
36 freopen("code/in.txt","r",stdin);
37 #endif
38 int cnt = 0 ;
39 for ( int i = 0 ; i < 19 ; i++)
40 {
41 cout<<prime[i]<<endl;
42 fflush(stdout);
43 cin>>st;
44 if (st=="yes") cnt++;
45 }
46 if (cnt>=2) puts("composite");
47 else puts("prime");
48 fflush(stdout);
49 #ifndef ONLINE_JUDGE
50 fclose(stdin);
51 #endif
52 return 0;
53}