説明

与えられた $a, b, p$ に対し $a^x \equiv b \pmod p$ を満たす非負整数 $x$ の最小値を求める。

計算量

  • $O(\sqrt p)$

実装例

  • mod_log($a$, $b$, $p$): $a^x \equiv b \pmod p$ を満たす非負整数 $x$ の最小値を返す。存在しない場合は $-1$。
int64_t mod_log(int64_t a, int64_t b, int64_t p) {
  int64_t g = 1;

  for(int64_t i = p; i; i /= 2) (g *= a) %= p;
  g = __gcd(g, p);

  int64_t t = 1, c = 0;
  for(; t % g; c++) {
    if(t == b) return c;
    (t *= a) %= p;
  }
  if(b % g) return -1;

  t /= g;
  b /= g;

  int64_t n = p / g, h = 0, gs = 1;

  for(; h * h < n; h++) (gs *= a) %= n;

  unordered_map< int64_t, int64_t > bs;
  for(int64_t s = 0, e = b; s < h; bs[e] = ++s) {
    (e *= a) %= n;
  }

  for(int64_t s = 0, e = t; s < n;) {
    (e *= gs) %= n;
    s += h;
    if(bs.count(e)) return c + s - bs[e];
  }
  return -1;
}

検証

AtCoder Regular Contest 042 D あまり

int64_t power(int64_t x, int64_t n, int64_t mod) {
  int64_t ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return ret;
}
 
signed main() {
  int x, p, a, b;
  cin >> x >> p >> a >> b;
 
  if(p <= a) {
    int k = a / p;
    a -= k * p;
    b -= k * p;
  }
 
  if((b - a + 1) <= 10000000) {
    int64_t ret = infll;
    auto tmp = power(x, a, p);
    for(int i = a; i <= b; i++) {
      ret = min(ret, tmp);
      tmp = tmp * x % p;
    }
    cout << ret << endl;
  } else {
    for(int i = 1;; i++) {
      int tmp = mod_log(x, i, p);
      if((a <= tmp && tmp <= b) || (a <= tmp + p && tmp + p <= b)) {
        cout << i << endl;
        break;
      }
    }
  }
}