mod/first_mod_range_of_linear.hpp

• View this file on GitHub
• Last update: 2024-01-02 21:42:22+09:00
• Include: #include "mod/first_mod_range_of_linear.hpp"

Depends on

• mod/min_of_linear_segments.hpp

Verified with

• test/mytest/first_mod_range_of_linear.test.cpp

Code

#include "mod/min_of_linear_segments.hpp"

// ax+b in {L, ..., R-1} mod となる最小の x>=0 を返す
// 例えば ax+b=1 なら ax+b in {-1} mod 2 のようにする
// 存在しなければ -1
int first_mod_range_of_linear(ll L, ll R, ll a, ll b, int mod) {
  assert(L <= R);
  b -= L, R -= L;
  if (R >= mod) return 0;
  a = bmod<ll>(a, mod), b = bmod<ll>(b, mod);
  // ax+b<R
  if (b < R) return 0;
  auto [X, DX] = min_of_linear_segments(a, b, mod);
  FOR(i, len(DX)) {
    ll x1 = X[i], x2 = X[i + 1];
    ll y2 = (a * x2 + b) % mod;
    if (y2 >= R) continue;
    ll y1 = (a * x1 + b) % mod;
    ll d = (y1 - y2) * DX[i] / (x2 - x1);
    ll k = floor(y1 - R, d) + 1;
    return x1 + k * DX[i];
  }
  return -1;
}

#line 2 "mod/min_of_linear_segments.hpp"

/*
ax + b (x>=0) が最小となるところの情報を返す。
prefix min を更新する x 全体が、等差数列の和集合。次を返す。
・等差数列の境界となる x_0, x_1, ..., x_n
・各境界の間での交差 dx_0, ..., dx_{n-1}
*/
pair<vc<int>, vc<int>> min_of_linear_segments(int a, int b, int mod) {
  assert(0 <= a && a < mod);
  assert(0 <= b && b < mod);
  vc<int> X = {0};
  vc<int> DX;
  int g = gcd(a, mod);
  a /= g, b /= g, mod /= g;
  // p/q <= (mod-a)/mod <= r/s
  int p = 0, q = 1, r = 1, s = 1;
  int det_l = mod - a, det_r = a;
  int x = 0, y = b;

  while (y) {
    // upd r/s
    int k = det_r / det_l;
    det_r %= det_l;
    if (det_r == 0) {
      --k;
      det_r = det_l;
    }
    r += k * p;
    s += k * q;
    while (1) {
      int k = max(0, ceil(det_l - y, det_r));
      if (det_l - k * det_r <= 0) break;
      det_l -= k * det_r;
      p += k * r;
      q += k * s;
      // p/q <= a/mod
      // (aq - pmod) = det_l を y から引く
      k = y / det_l;
      y -= k * det_l;
      x += q * k;
      X.eb(x);
      DX.eb(q);
    }
    k = det_l / det_r;
    det_l -= k * det_r;
    p += k * r;
    q += k * s;
    assert(min({p, q, r, s}) >= 0);
  }
  return {X, DX};
}
#line 2 "mod/first_mod_range_of_linear.hpp"

// ax+b in {L, ..., R-1} mod となる最小の x>=0 を返す
// 例えば ax+b=1 なら ax+b in {-1} mod 2 のようにする
// 存在しなければ -1
int first_mod_range_of_linear(ll L, ll R, ll a, ll b, int mod) {
  assert(L <= R);
  b -= L, R -= L;
  if (R >= mod) return 0;
  a = bmod<ll>(a, mod), b = bmod<ll>(b, mod);
  // ax+b<R
  if (b < R) return 0;
  auto [X, DX] = min_of_linear_segments(a, b, mod);
  FOR(i, len(DX)) {
    ll x1 = X[i], x2 = X[i + 1];
    ll y2 = (a * x2 + b) % mod;
    if (y2 >= R) continue;
    ll y1 = (a * x1 + b) % mod;
    ll d = (y1 - y2) * DX[i] / (x2 - x1);
    ll k = floor(y1 - R, d) + 1;
    return x1 + k * DX[i];
  }
  return -1;
}

Back to top page