問題
1以上1000以下の整数の秘密の数を当てる。
質問は200回まですることができて、質問では、
好きな自然数xに対して、秘密の数がxの倍数かどうかを聞くことができる。
秘密の数を当てよ。
方針
素数ごとにyes, noを聞く。
もし素数pでyesだったら、p^2, p^3, ...とnoになるまで聞く。
で、素数ごとにp^kまでがyesだったらp^kを全部掛ければよい。
const int MX = 1001;
bool p[MX];
int main(){
for(int i = 2; i * i < MX; i++) if(!p[i]) for(int j = i * i; j < MX; j += i) p[j] = 1;
int ans = 1;
for(int i = 2; i < MX; i++) if(!p[i]){
for(ll j = i; ans * i < MX; j *= i){
cout << "? " << j << endl;
string s; cin >> s;
if(s == "Y") ans *= i;
else break;
}
}
cout << "! " << ans << endl;
return 0;
}