题解：P14750 月影戀

· · 题解

题解：P14750 月影戀

前言

提供者绿名绿勾绿气球，难度绿题，状态AC绿还是很舒服的。(*￣w￣)′

一道思维题。

思路

你说得对，但是题意已经很清晰了。

我们来分析一下 h 的最大值：2 ^ {60} - 1。通过位运算常识，h 应该是 \operatorname{lowbit}(h) 的因数之一。进一步可推导出对于本题 h 的数据范围，则 \gcd(2^{60}, h) = \operatorname{lowbit}(h)。还可以得出若 \gcd(2^{60}, a) = 2^{60} 则 a = 2^{60}。只要原因是上面式子中的 a 应该不能再更大了，否则 2^{60} 应该是 a 的一个因数（或者说 a 是 2^{60} 的倍数）而且这两个值不相等。显然这是不可能的，因为就算是最小的倍数关系 2 倍也会超出本题范围（因为 2 ^ {61} > 2 ^ {61} - 1）。

我们重新来看 \gcd(a, b)，由于 b 不能为负数，所以我们先设 lb 为二进制位数，从低位起递推式升幅询问各位，每次询问 a = 2^{60} 以及 b = 2^{60} - lb。然后 b 加上 h。若返回 2^{60}，则说明 a = b，输出结果就可以完成本题。

代码

#include <bits/stdc++.h>
#define int long long
// 虽然在上文中强调了很多遍数据范围，但是十年OI一场空，______________。
using namespace std;
int t, lb, a, b = (1ll << 60); // 写 1ll 保持好习惯

signed main() {
    cin >> t;
    while (t--) {
        while (a != b) {
            lb += a;
            cout << "? " << b << " " << b - lb << "\n"; // 同思路
            cout.flush();
            cin >> a;
            cout.flush();
        }
        cout << "! " << lb << "\n"; // a 不等于 b 时就跳出循环直接输出
        lb = 0; a = 0;
    }

    return 0; // 完结撒花
}

后记

欢迎批评指错，期待与大家共同学习进步！ヾ(^▽^)