题解 AT_kupc2014_b 数当てゲーム

· · 题解

Solution

Examples

给出官方样例：

Ideas

可以找出 1 到 1000 的质数。

对于一个质数 i 提问 PIN 可否被 i 的 x 次方整除，若可以则答案乘以它，最终得到的也就是最小公倍数了。

可以直接乘，因为各质数是互质的。

可以发现这种方案 200 次是可以的。

Code

贴心批注版：

#include <iostream>
using namespace std;
int r=1, f;
int main(){
    for(int i=2; i<1001; ++i){ // PIN 是 1 到 1000 的整数
        f=0;
        for(int j=2; j*j<1+i; ++j) if(i%j==0){f=1; break;} // 质数检查，整除说明合数
        if(f<1){ // 说明是质数
            int h=i; // 当前要向 AI 提问的数字
            while(h<1001){
                cout<<"? "<<h<<'\n'; // 提问
                char state; cin>>state; // AI 的答案
                if(state=='Y') h*=i, r*=i; // Y 说明可以被整除，那么乘以这个质数
                else break; // 不能整除就去掉
            }
        }
    }
    cout<<"! "<<r<<'\n'; // 最终输出最小公倍数 r，at 不换行，爆 0 两行泪
    return 0;
}

纯洁无污染版：

#include <iostream>
using namespace std;
int r=1, f;
int main(){
    for(int i=2; i<1001; ++i){
        f=0;
        for(int j=2; j*j<1+i; ++j) if(i%j==0){f=1; break;}
        if(f<1){
            int h=i;
            while(h<1001){
                cout<<"? "<<h<<'\n';
                char state; cin>>state;
                if(state=='Y') h*=i, r*=i;
                else break;
            }
        }
    }
    cout<<"! "<<r<<'\n';
    return 0;
}

谢谢观看，有些不明白欢迎在评论区留言，我会一一回答。

小可的 19 号题解。纪念。