二次剩余用于解决在 模意义下开根 的问题:

题意

给定一个质数 $P$ 和一个非负整数 $N$,求 $x$ 使得

$$x^2 \equiv N (\text{mod } P)$$

本问题等价于求 $$\sqrt N ~(\text{mod } P)$$

性质

  1. 这个问题可能无解,如果有解,则有两个解,它们互为相反数

模版

// 求 sqrt(a) 在 mod P 下的值
// 调用 solve(a, P, r1, r2)
// 若有解,r1, r2 分别为两个解,其中 r1 小,r2 大
// 若无解,r1 == -1
namespace Quadratic_residue {
    ll qpow(ll a, ll b, ll P) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }

    bool check_if_residue(ll x, ll P) {
        return qpow(x, (P - 1) >> 1, P) == 1;
    }

    void solve(ll a, ll P, ll& r1, ll& r2) {
        if (a <= 1) {
            r1 = a, r2 = P - a; return;
        }
        if (!check_if_residue(a, P)) {
            r1 = -1; return;
        }
        ll x;
        while (1) {
            x=1ll*rand()*rand()%P;
            if (qpow((x*x-a+P)%P,(P-1)/2, P)!=1) break;
        }
        ll w=(x*x-a+P)%P;
        pll res = {1,0}, t = {x,1};
        auto Mul=[&](pll a,pll b){ // 复数乘法
            ll x=(1ll*a.first*b.first+1ll*a.second*b.second%P*w)%P;
            ll y=(1ll*a.first*b.second+1ll*a.second*b.first)%P;
            return make_pair(x,y);
        };
        ll d=(P+1)/2;
        while (d) {
            if(d&1) res=Mul(res,t);
            t=Mul(t,t);
            d>>=1;
        }
        ll r = (res.first % P + P) % P;
        r1 = min(r, (P - r) % P);
        r2 = max(r, (P - r) % P);
    }
};

参考链接

  1. https://chasingdeath.github.io/articles/2020/08/15/2244ecc3.html (模版来源)
  2. https://www.luogu.com.cn/problem/P5491