Hint

Hint 1：首先，不考虑拜日教皇骗人的情况，我们如何准确查询？

Hint 2：当我们学会了不骗的人情况下准确查询后，如何知道拜日教皇有没有骗人呢？

Sol

之后的分析以及代码均由 $0$ 作为起始下标。

先考虑 Hint 1。

我们发现，$2^{31}-1=2,147,483,647$。

也就是说，$10^9$ 只需要大约 $30$ 个 bit 即可。

我们枚举每个 bit 表示的实际数字并查询。检查返回值与 $cnt$ 的大小关系。

如果返回值比 $cnt$ 小，说明这个 bit 被消除了，也就是原数的这个 bit 是 $1$。

举个例子：$(10)_{10}=(1010)_2$。

$(10-2)_{10}=(8)_{10}=(1000)_2$。

这里我们消去第 $1$ 个 bit，也就是消去了 $2^1=2$。

$f(8)<f(10)$，第 $1$ 个 bit 确实是 $1$。

$(10-1)_{10}=(9)_{10}=(1001)_2$

这里我们消去第 $0$ 个 bit，也就是消去了 $2^0=1$。

$f(9)=f(10)$，第 $0$ 个 bit 不是 $1$。

所以退位什么只会导致 $1$ 个数相同或更多。感兴趣的话可以多找点例子。

综上，我们枚举 $0\sim 29$ 每一个 bit 代表的数 $x$ 并查询。如果得到的结果比 $cnt$ 小，那么 $ans\gets ans+x$，答案加上 $x$。

至此，Hint 1 的解决方法结束。

for(int i=0;i<30;i++)
{
    cout<<"? "<<(1<<max(i-1,0))<<'\n';
    fflush(stdout);
    int c;
    cin>>c;
    if(c==0)bit++,ans|=1<<i;
    if(bit==cnt)break;
}

如何处理 Hint 2 所提到的骗人情况呢？

我们发现题目中给了 $60$ 次的询问限制，而 Hint 1所提到的只有 $30$ 次询问。

我们发现，如果每次 ? 0 $f(n-x)$ 永远不变，一定是 $cnt$。也就是说，一旦返回不是 $1$，也就是不相等，那么一定骗人了。

因此，我们查询 $m$ 次 ? 0。因为骗人有周期性，所以想知道之后第 $i$ 条询问的回答是否骗人只需查看第 $i\bmod m$ 个询问的结果。

Code

/*
Auther:  cyx2009
Luogu:   516346
QQ:      2176807108
*/
#include<bits/stdc++.h>
using namespace std;
bool f[50];//是否说谎 
int cnt,m;
int ans,bit; 
int main()
{
	cin>>cnt>>m; 
	for(int i=0;i<m;i++)
	{
		cout<<"? 0\n";
		fflush(stdout);
		int x;
		cin>>x;
		if(x!=1)f[i]=0;
		else f[i]=1;
	}
    for(int i=0;i<30;i++)
    {
        cout<<"? "<<(1<<max(i-1,0))<<'\n';
        fflush(stdout);
        int c;
        cin>>c;
        if(!f[i%m])c=(c+1)%3; 
        if(c==0)bit++,ans|=1<<i;
        if(bit==cnt)break;
        // cout<<bit<<"\n"; 
      	// fflush(stdout);
    }
    cout<<"! "<<ans<<'\n';
    fflush(stdout);
    return 0;
}

Nothing

说句闲话，这题是一道大杂烩的原题。

主体部分（Hint 1）为 CF1780D，另一部分（Hint 2）为 CF1010B。

在写下这段的时候，这两题在 CF 的评分均为 *1800，融合之后的这题，个人认为难度放到提高组也是不为过的。

至于为什么出交互，可能是受到了「信息与未来 2022」启发。小学生比赛都能出交互，普及组模拟赛不能出吗？