题目大意：
题目：未知一个数 (a)，让你每次猜两个数 (x) 和$ y$，若 ((xmod a)ge (ymod a)) 返回 x，否则返回 y。让你猜测次数少于60次的时候猜出数 (a)。
题解：
交互题，这个算是我最不会写也不太想写的题目之一了。
还是有点难的，接下来说说我看了这么多的博客之后的想法。
首先很容易的发现这个就是一个周期为a的函数，图像如上。
所以每次找 (i) ，如果 (i*2mod\,a <=imod\,a) ，那么显然易见，在区间 ([i,i*2]) 有且仅有一个值 $xmod,a = 0 $ ，那么从小到大找到的第一个 (x)，这个 (x=a)。
接下来贴一下证明：https://www.cnblogs.com/ttttttttrx/p/10800618.html
好像不是那么容易理解，接下来我简单说说。
- (amod \,b<a/2(a>=b)) ，(a-b*k=x)
- 其中 (b*k>=a/2) ，应该可以缩小成 (b*k>a/2)，这个是因为如果(b*k<=a/2) ，那么 (2*b*k<=a)，所以 (b*k>a/ 2)， 所以 (x<a/2)
- 所以 (amod\,b<a/2(a>=b))
- 如果 (a<b) ，那么 (amod \,b<a/2(a>=b)) 一定不成立，因为 (amod\,b=a>a/2)
- 综上所述，从小到大找，找到的第一个 (i*2mod\,a <=imod\,a) ，那么 (a) 一定在区间 ([i,2*i]) 之间
- 最后说说为什么是每次找 ([2^i,2^{i+1}]) ，因为如果 ([2^{i-1},2^i]) 没有找到，说明 (2^i<a) 那么 区间 ([2^i,2^{i+1}]) 一定最多一个点 (x)，使得 (xmod\,a=0)
所以说，如果找到了一个 (i*2mod\,a <=imod\,a) ，那么 (i*2>a) 一定成立。
这个之后就是一个二分，这个二分比较特别，因为我已经知道 (imod\,a>i*2mod\,a) ，并且 (2*i>a & i<a) ，所以我每次枚举 ([mid,r])
如果结果是 (r)，那么说明已经应该是 (r) 变小，如果结果是 (mid) 那么说明 (l) 可以变大，自行领悟吧。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
typedef long long ll;
char s[10];
int main(){
while(true){
scanf("%s",s+1);
if(s[1]=='s'){
ll l = 0,r = 1;
for(int i=1;i<=35;i++){
printf("? %lld %lld
",l,r);
fflush(stdout);
scanf("%s",s+1);
if(s[1]=='x') break;
//如果等于x，表示i mod a > i*2 mod a
l = r,r <<= 1;
}
ll ans=0;
while(l<=r){
ll mid=(l+r)>>1;
printf("? %lld %lld
",mid,r);
fflush(stdout);
scanf("%s",s+1);
if(mid+1==r){
if(s[1]=='x') ans = r;
//如果 mid mod a > r mod a，因为答案ans一定是 ans%a = 0，所以更小的这个应该是答案
else ans = mid;
break;
}
else if(s[1]=='x') l = mid;
else r = mid;
}
printf("! %lld
",ans);
fflush(stdout);
}
else break;
}
return 0;
}
/*
input
start
x
x
start
x
x
y
start
x
x
y
y
end
output
? 0 0
? 10 1
! 1
? 0 0
? 3 4
? 2 5
! 2
? 2 4
? 2 5
? 3 10
? 9 1
! 3
*/