CF1114E Arithmetic Progression 题解

题意：

这是一道交互题。

有一个长度为 $n$ 的序列 $a$，保证它从小到大排序后是个等差数列。

你不知道这个序列长什么样，但你可以询问：

$\texttt{? i}$ 表示询问 $a_i$ 的值；

$\mathtt{>\ x}$ 表示询问序列中是否存在严格大于 $x$ 的数。

你可以问不超过 $60$ 个询问。

现在，你需要求出这个等差数列的首项和这个等差数列的公差。

数据范围：

$2\le n\le 10^6,~0\le a_i\le 10^9$。

注意到操作二可以让我们二分出序列的最大值，记为 $a_n$ （就当题目的序列没有名字好了）。

那么接下来的询问只能问询问一了，因为询问二根本问不出什么东西，这不明摆着让我们乱搞么？

考虑把所有剩下的询问都用于操作一，记询问得到的数为 $x_1,x_2,\cdots,x_k$ 。由于

$d\mid\gcd\{a_n-x_1,\,a_n-x_2,\,a_n-x_3,\,\cdots,\,a_n-x_k\}$

显然 $k$ 越大，$d$ 越可能等于 $\gcd$ 的值，可是这道题又限制了我们问的 $k$ 的大小。

因此考虑随机化，即随机一个排列，然后把排列的前 $k$ 项（$k$ 是剩余询问数）用于询问。

最后直接将 $\gcd\{a_n-x_1,\,a_n-x_2,\,a_n-x_3,\,\cdots,\,a_n-x_k\}$ 当作 $d$ 输出即可。

分析一下正确率。首先二分最大值的花费不超过 $\left\lceil\log_2 10^9\right\rceil=30$ 次，即 $k \ge 30$ 次。

记首项 $a_1 = a_0 + d$ ，那么 $x_i = a_0 + b_id$ ，而题目保证是等差数列，所以 $b_i$ 是一个 $1$ 到 $n$ 的排列。

那么错误概率为

$p=\frac{1}{n^{\underline{k}}} \sum_{b\, \in \,\mathrm{permutation}(n)}\left[\gcd\left(b_1, \ldots, b_k\right)=1\right]$

这里的下划线是下降阶乘幂。

考虑枚举最大公约数 $d$ ，根据莫比乌斯反演有

$\frac{1}{n^{\underline{k}}} \sum_{d=2}^n \mu(d)\left\lfloor\frac{n}{d}\right\rfloor^{\underline{k}}$

这个东西可以 $\mathcal{O}(n)$ 算出来，我用 Python 算的，代码在后面。

算出来答案是 $9.309223788847006\times 10^{-10}$ ，这个错误率低的比某些哈希还低。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

int p[N]; mt19937 rd(time(0));
int ask(int x) { cout << "? " << x << endl; cin >> x; return x; }
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    if(n <= 60)
    {
        int mx = 0, mn = INF;
        rep(i, 1, n) { int x = ask(i); up(mx, x); down(mn, x); }
        cout << "! " << mn << ' ' << (mx - mn) / (n - 1) << endl; return 0;
    }
    int l = 0, r = 1e9, cnt = 0;
    for(int mid, tmp; l < r; )
    {
        mid = (l + r) >> 1; cout << "> " << mid << endl;
        ++cnt; cin >> tmp; !tmp ? r = mid : l = mid + 1;
    }
    int mx = l, ans = 0;
    rep(i, 1, n) p[i] = i; shuffle(p + 1, p + 1 + n, rd);
    rep(i, 1, min(n, 60 - cnt)) ans = gcd(ans, mx - ask(p[i]));
    cout << "! " << (mx - (n - 1) * ans) << ' ' << ans << endl;
    return 0;
}

算错误率的代码：

def mobius(n):
    mu = [0] * (n + 1)
    ck = [False] * (n + 1)
    prime = []
    cnt = 0
    
    mu[1] = 1
    for i in range(2, n + 1):
        if ck[i] != True:
            prime.append(i)
            mu[i] = -1
            ++cnt
        for j in range(cnt):
            if i * prime[j] > n:
                break
            pos = i * prime[j]
            ck[pos] = True
            if i % prime[j] == 0:
                mu[pos] = 0
                break
            else:
                mu[pos] = -mu[i]
    return mu

mu = mobius(10 ** 6)
n = 10 ** 6
k = 30
ans = 0
for d in range(2, n):
    tmp = 1
    for j in range(k):
        tmp = tmp * ((n // d) - j) / (n - j)
    ans = ans + tmp
print(ans)