CF1103B Game with modulo

CF1103B Game with modulo 题目大意

未知一个数 a a a，让你每次猜两个数 x x x 和 y y y，若 ( x   m o d   a ) ≥ ( y   m o d   a ) (xbmod a)ge (ybmod a) (xmoda)≥(ymoda) 返回 x，否则返回 y。

让你猜测次数少于 60 60 60 次的时候猜出数 a a a。

解题思路

我们可以先二分猜一个 x x x，如果 ( 2 x   m o d   a ) ≥ ( x   m o d   a ) (2xbmod a) ≥ (x bmod a) (2xmoda)≥(xmoda) ， 那么我们就能确定 x < = a < = 2 x x <= a <= 2x x<=a<=2x。

找到 a a a 的范围后，可以再来一个二分求出 a a a。

具体见代码。

CODE

#include 

#define int long long

using namespace std;

string s;

int len;

signed main()
{
    cin >> s;
    while (s.size() != 3 && s.size() != 7)
    {
        int l = 0, r = 1;
        do
        {
            printf("? %lld %lldn", l, r);
            cin >> s;
            if (s[0] == 'y')
            {
                l = r;
                r <<= 1;
            }
        } while (s[0] == 'y');
        while (l + 1 < r)
        {
            int mid = (l + r) >> 1;
            printf("? %lld %lldn", mid, l);
            cin >> s;
            if (s[0] == 'x')
                l = mid;
            else
                r = mid;
        }
        printf("! %lldn", l + 1);
        cin >> s;
    }
    return 0;
}