src/math/modular-arithmetic/mod-sqrt.hpp

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00
Include: #include "src/math/modular-arithmetic/mod-sqrt.hpp"

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"
#include "src/modular-arithmetic/mod-pow.hpp"

namespace luz {

  // a^{(p-1)/2} == 1 (mod p, p is prime)
  //   iff. a has sqrt on mod p.
  // [!] mod-sqrt is not always unique.
  // O(log^2 p)
  i64 mod_sqrt(i64 a, i64 p) {
    if (a == 0) return 0;
    if (p == 2) return a;
    if (mod_pow(a, (p - 1) >> 1, p) != 1) return -1;

    i64 b = 1;
    while (mod_pow(b, (p - 1) >> 1, p) == 1) ++b;

    i64 e = 0, m = p - 1;
    while (m % 2 == 0) m >>= 1, ++e;

    i64 x = mod_pow(a, (m - 1) >> 1, p);
    i64 y = a * (x * x % p) % p;
    (x *= a) %= p;
    i64 z = mod_pow(b, m, p);
    while (y != 1) {
      i64 j = 0, t = y;
      while (t != 1) {
        j += 1;
        (t *= t) %= p;
      }
      z = mod_pow(z, i64(1) << (e - j - 1), p);
      (x *= z) %= p;
      (z *= z) %= p;
      (y *= z) %= p;
      e = j;
    }
    return x;
  }

}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: src/modular-arithmetic/mod-pow.hpp: line -1: no such header