题目

传送门

思路

首先我们很明显可以知道 \(x<2*x\)

在\(x,2*x<a\)的情况下

\(x\%a<2x\%a\)

如果在\(x<a但2*x>a\)的情况下

\(x\%a>2x\%a\)

所以我们就可以用这个性质

用倍增将a的范围求出来

之后再细致的二分缩小a的范围即可

注意\(a==1和a==2\)是两种特殊情况

代码

#include<iostream>
using namespace std;
#define int long long
string opt;
string c;
signed main()
{
    //ios::sync_with_stdio(false);
    while(1)
    {
        cin>>opt;
        if(opt[0]=='e')
            break;
        int l=0;
        int r=2e9;
        int mid=1;
        while(1)
        {
            cout<<"? "<<mid<<' '<<min(2000000000ll,mid*2)<<'\n';
            //fflush(stdout);
            cin>>c;
            if(c[0]=='x')
            {
                l=mid;
                r=min(1000000000ll,mid*2);
                break;
            }
            mid*=2;
        }   
        while(l+1<r)
        {
            mid=(l+r)>>1;
            cout<<"? "<<mid*2<<' '<<mid<<'\n';
            fflush(stdout);
            cin>>c;
            if(c[0]=='x')   
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        if(r==2)
        {
            cout<<"? 2 1"<<'\n';
            fflush(stdout);
            cin>>c;
            if(c[0]=='y')
            {
                cout<<"! 2"<<'\n';
                fflush(stdout);
            }
            else
            {
                cout<<"! 1"<<'\n';
                fflush(stdout);
            }
        }
        else
        {
            cout<<"! "<<r<<'\n';
            fflush(stdout);
        }
    }
    return 0;
}

习题：Game with modulo

原文：https://www.cnblogs.com/loney-s/p/12261422.html