Codeforces 1104 D（数论+二分+交互）

传送门

题意：

让你在$60$步之内猜出一个模数$a$。每次你可以输入两个数$x$和$y$。如果$x\mathrm{m}\mathrm{o}\mathrm{d}a\ge y\mathrm{m}\mathrm{o}\mathrm{d}a$，则交互器输出"$X$"，否则输出“$Y$”.

题目分析：

平日里遇到交互题的机会不多，正好借着CF的机会练习一下这类题目。

对于交互题这类题，一般都是运用二分的方法，不断逼近最优解进而解决问题。（最经典的交互题就是二分猜数问题）。

言归正传，对于这个题，我们不光要运用二分去解决，而且还需要用二进制试探法。

---

所谓二进制试探法，就是分别用[0,1],[1,2],[2,22],[22,23]......[2k,2k+1][0,1],[1,2],[2,2^2],[2^2,2^3]......[2^{k},2^{k+1}][0,1],[1,2],[2,22],[22,23]......[2k,2k+1]，这些的区间将答案的区间进行缩小。而如果我们成功缩小到某个区间$[a,b]$时，我们就可以用二分答案去求解。

---

对于这个问题，我们比较容易发现，当我们进行二进制试探的时候，存在一个区间$[v,2v]$$$v\mathrm{m}\mathrm{o}\mathrm{d}a\ge 2v\mathrm{m}\mathrm{o}\mathrm{d}a$$成立，则必有$$a\in [v,2v]$$简单证明：因为$a\ge v$则必有$v\mathrm{m}\mathrm{o}\mathrm{d}a=v$，而又因为$a\le 2v$，则根据取模的性质，必有$2v\mathrm{m}\mathrm{o}\mathrm{d}a<v$。

因此我们可以知道，倘若在我们二进制试探的时候，遇到了一个区间$[l,r]$，能够让交互器输出“$X$”，则我们就可以确定答案必定在$[l,r]$的范围内。而这个过程极限会询问$30$次。

此后，我们就可以在这个区间内进行二分。

倘如当前的枚举的区间为$[l,mid]$，如果此时 $$l\mathrm{m}\mathrm{o}\mathrm{d}a\ge mid\mathrm{m}\mathrm{o}\mathrm{d}a$$ 则说明$mid>a$，即答案仍比当前的右区间$r$小，因此我们可以将右区间左移；反之，则将左区间右移。

#include <bits/stdc++.h>
using namespace std;
string str;
int main()
{
    cin>>str;
    int l=0,r=1;
    while(str!="end"){
        l=0,r=1;
        printf("? %d %d\n",l,r);
        cin>>str;
        while(str=="y"){
            l=r,r<<=1;
            printf("? %d %d\n",l,r);
            fflush(stdout);
            cin>>str;
        }
        while(l+1<r){
            int mid=(l+r)>>1;
            printf("? %d %d\n",l,mid);
            fflush(stdout);
            cin>>str;
            if(str=="y") l=mid;
            else r=mid;
        }
        printf("! %d\n",l+1);
        fflush(stdout);
        cin>>str;
    }
    return 0;
}