D. Game with modulo
题目链接：https://codeforces.com/contest/1104/problem/D
题意：
这题是一个交互题，首先一开始会有一个数a，你最终的目的是要将它猜出来。
每次询问会输出"? x y"，然后有：
- "x" (without quotes), if (x % a)≥(y % a).
- "y" (without quotes), if (x % a)<(y % a).
最多给你60次询问的机会，问最后这个a是多少。
题解：
这里会用到取余的性质，假设现在有一个数b，现在有b%a=c。假设a>b那么我们什么都不用管；假设a<=b，我们可以推出c是满足c<a/2的。
也就是说，当x,y都小于a时，必定会输出"y"；否则，至少有y<a/2。
那么我们想到一开始令x=1,y=2进行倍增，因为当y=2*x时，若y>a，则有y%a<x%a恒成立，此时也x也是必定小于a的。
那么我们可以通过这个确立一个区间，然后在区间里面进行二分来询问a的值就好了。
注意一下a=1以及a=2时的特殊情况。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = ;
string s;
int query(ll x,ll y){
printf("? %I64d %I64d\n",x,y);
fflush(stdout);
char c;
getchar();
scanf("%c",&c);
if(c=='x'){
return ;
}else return ;
}
int main(){
while(cin>>s){
if(s=="end") break ;
ll a=,b=;
if(query(a,b)==){
if(query(,)==) printf("! 1\n");
else printf("! 2\n");
continue ;
}
while(query(a,b)){
a*=;
b*=;
if(b>=mx){
b=mx;
break ;
}
}
ll l=a+,r=b+,mid;
while(l<r){
mid=l+r>>;
if(query(a,mid)) l=mid+;
else r=mid;
}
printf("! %I64d\n",r);
}
return ;
}