题目大意
存在一个打乱了顺序的等差数列 \(a\)，你可以询问不超过 \(60\) 次，每次可以以以下两种方式之一进行询问：
-
查询 \(a\) 中是否有严格大于 \(x\) 的数。
-
查询 \(a_i\) 的值。
你需要求出这个等差数列的首项和公差。
思路分析
比较有意思的题。
看到第一种询问，首先想到二分，我们可以用 \(O(\log V)\) 次询问查询出 \(a\) 中的最大值。
那么公差怎么求呢？
考虑随机化，我们在 \(a\) 中随机询问若干个位置的值（把剩下的询问次数全部询问掉），然后将这些得到的值排序，求相邻两数之间的差，再求出所有差的最大公约数作为 \(a\) 的公差，这样有极大概率是对的。
证明可以参考官方题解，用莫反可以得出出错的概率约为 \(1.86185\times 10^{-9}\)。证明我也不会。
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <random>
#include <chrono>
#include <cmath>
using namespace std;
const int V=1000000000,N=100,M=60;
int n,times,tot,in1;
int a[N],d[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
std::mt19937 defaultRNG(std::chrono::steady_clock::now().time_since_epoch().count());
int defaultRandInt(int l,int r){
int out=defaultRNG()%(r-l+1)+l;
return out>=l?out:out+r-l+1;
}
int (*randint)(int,int)=defaultRandInt;
int main(){
scanf("%d",&n);
int l=0,r=V,ans=0;
while(l<=r){
int mid=(l+r)>>1;
cout<<"> "<<mid<<endl;
times++;
scanf("%d",&in1);
if(in1) l=mid+1,ans=mid;
else r=mid-1;
}
for(int i=times;i<M;i++){
cout<<"? "<<randint(1,n)<<endl;
scanf("%d",&a[++tot]);
}
sort(a+1,a+tot+1);
for(int i=2;i<=tot;i++)
d[i-1]=a[i]-a[i-1];
int D=d[1];
for(int i=2;i<tot;i++)
D=gcd(D,d[i]);
cout<<"! "<<ans+1-D*(n-1)<<' '<<D<<endl;
return 0;
}