Codeforces Round #538 (Div. 2) E. Arithmetic Progression

题目大意

这是一道交互题。

给出一个长度为 n n n的等差数列 x i x_i xi​，对其进行重新排序等于一个新的数列 a i a_i ai​。

有两种询问：

1.数列中是否存在大于 x x x的数。

2. a i a_i ai​是多少。

需要在不超过 60 60 60次询问下，找到数列 x i x_i xi​的公差和第一项。

时间限制

2s

数据范围

n ≤ 1 0 6 n\le10^6 n≤106

x i , a i ≤ 1 0 9 x_i,a_i\le10^9 xi​,ai​≤109

题解

很显然，利用第一个询问就可以通过二分找到数列中最大的元素，

那么如何在剩下的 30 30 30次左右的询问中找到公差呢。

首先，要知道公差的一个性质： ∀ ( i , j , i < j ) d ∣ x j − x i \forall (i,j , i < j) d|{x_j-x_i} ∀(i,j,i<j)d∣xj​−xi​

于是 d = g c d ( x j − x i ) d=gcd\pod{x_j-x_i} d=gcd(xj​−xi​)

如果那 30 30 30次询问足够随机，那么通过计算两两差值的最大公约数就可以求出 d d d。

不过实际的公差也有可能是 d d d的某个约数，这里可以稍微特判一下，

如果通过已知的最大值和当前知道的公差计算出来的第一项不满足题意，比如：小于0，或者大于已知的最小值，就要稍微调整一下。

Code

//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#define G getchar
#define ll long long
using namespace std;

int read()
{
    char ch;
    for(ch = G();(ch < '0' || ch > '9') && ch != '-';ch = G());
    int n = 0 , w;
    if (ch == '-')
    {
        w = -1;
        ch = G();
    } else w = 1;
    for(;'0' <= ch && ch <= '9';ch = G())n = (n<<1)+(n<<3)+ch-48;
    return n * w;
}

const int N = 1000005;
int l , r , mid;
int n , tmp , m , a[100] , d , cnt , pos;
bool bz[N];
int mi , ans , ansd;

int gcd(int a , int b)
{
    if (a % b) return gcd(b , a % b); else return b;
}

int main()
{
    //freopen("f.in","r",stdin);
    //freopen("f.out","w",stdout);

    n = read();
    l = 0;
    r = 1000000000;
    for ( ; l < r ; )
    {
        mid = (l + r) / 2;
        printf("> %d\n", mid);
        fflush(stdout);
        tmp = read();
        if (tmp) l = mid + 1; else r = mid;
        m++;
    }

    cnt = 1;
    a[1] = r;
    pos = r % n + 1;

    for ( ; m < 60 && cnt <= n; m++)
    {
        printf("? %d\n", pos);
        fflush(stdout);
        bz[pos] = 1;
        cnt++;
        a[cnt] =read();
        pos = pos * 3 % n + 1;
        for ( ; bz[pos] && cnt <= n; ) pos = pos % n + 1;
    }

    d = 0;
    for (int i = 1 ; i <= cnt ; i ++)
        for (int j = 1 ; j < i ; j++)
            if (a[i] != a[j]) d = gcd(d , abs(a[i] - a[j]));

    mi = r;
    for (int i = 1 ; i <= cnt ; i++)
        mi = min (mi , a[i]);

    for (int i = 1 ; i * i <= d ; i++)
        if (d % i == 0)
        {
            tmp = r - (n - 1) * i;
            if (0 <= tmp && tmp <= mi)
            {
                ans = tmp;
                ansd = i;
                break;
            }

            tmp = r - (n - 1) * (d / i);
            if (0 <= tmp && tmp <= mi)
            {
                ans = tmp;
                ansd = d / i;
                break;
            }
        }

    printf("! %d %d\n", ans , ansd);
    fflush(stdout);

    return 0;
}