【exgcd】【P7849】

一扶苏一 · 2021-09-12 13:48:30 · 题解

Analysis

考虑数列是乱序的，询问从哪个数开始都是一样的，因此我们不妨考虑询问 A_1 和 A_2 在模意义下的值，并不妨设 A_1 < A_2。

从第三个数开始，依次询问每个数和 A_1、A_2 的大小关系，则与 A_1、A_2 的大小关系不同的位置就是大于 A_1 且小于 A_2 的个数，不妨记为 k’，又 k = k' + 1，则公差 d 满足如下关系：A_2 \equiv A_1 + kd(\bmod p)，即 kd + pt = A_2 - A_1，其中 k 和 p 已知。显然 k 和 p 互质，使用 exgcd 解这个方程即可。

查询次数为 2 + 2\times(n - 1) + 1 = 2n - 1 次。最后加上的 1 是查询 A_1 和 A_2 的大小关系。

使用 exgcd 解上述方程的方法是：先解出 kd' + pt' = 1 的解，然后令 d = d' \times (A_2 - A_1)、t = t' \times (A_2 - A_1) 即可。

Code

#include <iostream>
#include <algorithm>

const int maxn = 1000005;
const int p = 1000000007;

typedef long long int ll;

int n, q, x, y, z;
int a[2][maxn];

void exgcd(ll a, ll b, ll &xx, ll &yy) {
  if (b == 0) {
    yy = 0; xx = 1;
    return;
  }
  exgcd(b, a % b, yy, xx);
  yy -= xx * (a / b);
}

int main() {
  std::cin >> n >> q;
  for (int i = 3; i <= n; ++i) {
    std::cout << "> 1 " << i << std::endl;
    std::cin >> a[0][i];
    std::cout << "> 2 " << i << std::endl;
    std::cin >> a[1][i];
  }
  int cnt = 0;
  for (int i = 1; i <= n; ++i) if (a[0][i] != a[1][i]) ++cnt;
  std::cout << "? 1" << std::endl;
  std::cin >> x;
  std::cout << "? 2" << std::endl;
  std::cin >> y;
  std::cout << "> 1 2" << std::endl;
  std::cin >> z;
  if (z == 1) std::swap(x, y);
  if (x > y) y += p;
  ll d, t;
  exgcd(cnt + 1, p, d, t);
  d = (d % p + p) % p;
  std::cout << "! " << (d * (y - x) % p) << std::endl;
}