lib/math/sqrt.hpp

View this file on GitHub
Last update: 2025-05-22 02:52:27+09:00
Include: #include "lib/math/sqrt.hpp"

Depends on

Verified with

Code

#pragma once
#include <concepts>
#include "math/modint.hpp"

template <class mint>
requires(std::derived_from<mint, internal::modint_base>)
bool has_sqrt_mod(mint x) {
    return x == 0 || x.pow(mint::mod() / 2) == 1;
}

template <class mint>
requires(std::derived_from<mint, internal::modint_base>)
mint sqrt_mod(mint x) {
    const int p = mint::mod();
    if (x == 0 || x == 1) return x;
    if (p % 4 == 3) return x.pow(p / 4 + 1);
    int q = p - 1, s = 0;
    while (~q & 1) q >>= 1, ++s;
    mint z(1);
    while (has_sqrt_mod(z)) ++z;
    mint c = z.pow(q);
    mint t = x.pow(q);
    mint r = x.pow(q / 2 + 1);
    while (t != 1) {
        int m = 0;
        mint u = t;
        while (u != 1) ++m, u *= u;
        while (s != m) {
            --s;
            if (s == m) r *= c;
            c *= c;
        }
        t *= c;
    }
    return r;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: math/modint.hpp: line -1: no such header