异次元空间_牛客博客

对于每个空间需要的天数满足公式 (初始值 + 天数 * 每天增长量) % p = k ，即

$(a[i] + day[i] * d[i]) \ mod \ p = k \tag{1}$

上面的式子等价于：

$day[i] * d[i] \equiv (k - a[i])(mod \ p) \tag{2}$

等式的两端同乘以 d[i] 的逆元：

$day[i] \equiv (k - a[i])* d[i]^{-1}(mod \ p) \tag{3}$

问题就变成了如何求 d[i] 的逆元，我们令 x 表示 d[i] 的逆元：

$x * d[i] \equiv 1 (mod \ p) \tag{4}$

因为 p 为质数，所以保证了 gcd(d[i], p) = 1 ，由扩展欧几里的算法，可以得到：

$x * d[i] + y * p = 1 \tag{5}$

当我们求出了 x 之后，自然可以通过公式(4)计算出 day[i] 。

LL exgcd(int a, int b, LL& x, LL& y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  LL d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}

int solve(int n, int m, int p, vector<int>& a, vector<int>& d, int k) {
  vector<int> record(n);
  for (int i = 0; i < n; ++i) {
    if (a[i] == k)
      record[i] = 0;
    else {
      LL x, y;
      LL g = exgcd(d[i], p, x, y);
      LL times = k - a[i];
      record[i] = (times * x % p + p) % p;
    }
  }
  sort(record.begin(), record.end());
  return record[m - 1];
}