Arithmetic Progression 题解

Arithmetic Progression

题目大意

存在一个打乱了顺序的等差数列 \(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;
}