模板 - Legendre 符号 & 二次剩余

理论笔记

基于 C++17 标准,对给定的整数 \(n,p\), 若 \(\left(\frac{n}{p}\right)\ne1\) 则返回 std::nullopt, 否则返回方程 \(x^2\equiv n\pmod p\) 的一个根

代码中使用了 __builtin_ctzll

https://cplib.tifa-233.com/src/code/nt/qresidue.hpp 存放了笔者对该算法 / 数据结构的最新实现,建议前往此处查看相关代码

代码

Show code