题解 CF679A 【Bear and Prime 100】

· · 题解

发题解的人好少啊，那我来发一篇吧
这道题有不少陷阱，作为蒟蒻的我被坑了许多(>=2)回QWQ
首先要判断隐藏数(闭合区间[2,100])，我们可以问20个问题。
而100以内的合数肯定会被50以内的多(>=2)个素数整除，例如98可以被2和7整除（本文讨论的整除不包括被1和数的本身整除）。所以马上我们就可以整理出我们的“问题列表”

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 (共15个)

然后我们就这样写出代码，提交，最后…… WA!，为什么呢？
因为上面的问题对于平方数不适用，例如49只能被7整除，所以我们要再增加针对平方数的问题。

4,9,25,49

注意：不增加36，36虽然是平方数，但是它能被2,3,6整除，不需要针对提问。
现在我们有了一个大概的思路：输出问题，接收回答，当"yes"数大于或等于2时，输出"composite"（合数），否则输出"prime"。
下面上代码，供参考：（译者提供了模板）

#include <iostream>
using namespace std;
const int q[19]={2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49}; //问题列表
int main()
{
    char ans[4];  //答案
    int cnt=0;  //计数
    for(register int i=0;i<19;i++)  //逐个提问
    {
        cout<<q[i]<<endl;  //提问
        fflush(stdout);  //刷新流
        cin>>ans;  //接收回答
        if(ans[0]=='y') cnt++;  //统计
        if(cnt>=2)  //"yes"数>=2,为合数
        {
            cout<<"composite"<<endl;  //输出判断
            fflush(stdout);
            return 0;  //直接退出
        } 
    }
    cout<<"prime"<<endl;  //输出判断
    fflush(stdout);
    return 0;
}

求通过……