Mod Sqrt

modSqrt(a) finds one x such that x^2 = a over a modint type.

It returns some(x) when a square root exists, and none otherwise.

Import

import std/options
import atcoder/modint
import atcoder/extra/math/mod_sqrt

Example

import std/optionsimport atcoder/modintimport atcoder/extra/math/mod_sqrttype mint = modint998244353let r = modSqrt(mint(4))doAssert r.isSomelet x = r.getdoAssert x * x == mint(4)

Return value

Option[T]

Use std/options helpers such as isSome, isNone, and get.

Notes

• The modulus is assumed to be prime.
• If two square roots exist, one of them is returned.
• If no square root exists, the result is none.

Complexity

For modulus p, the running time is roughly:

• O(log^2 p)