定义：对于n、p，若存在x，使得 x 2 ≡ n ( m o d p ) x^2\equiv n(mod\ p) x2≡n(mod p)，则称n为模p意义下的二次剩余。 也就是说，如果n是模p的二次剩余。那么 n m o d p \sqrt n\ mod\ p n mod p，可以用二次同余方程的解 x x x 来代替 n \sqrt n n ，暴力地找就是 x 2 % p = = n x^2\%p==n x2%p==n
( n p ) = { 1 n 是 模 p 意 义 下 的 二 次 剩 余 − 1 n 是 模 p 意 义 下 的 二 次 非 剩 余 0 n ≡ 0 ( m o d p ) (\frac np)=\begin{cases} 1 & n是模p意义下的二次剩余 \\ -1 &n是模p意义下的二次非剩余\\ 0& n\equiv 0 (mod\ p) \end{cases} (pn)=⎩⎪⎨⎪⎧1−10n是模p意义下的二次剩余n是模p意义下的二次非剩余n≡0(mod p)
( n p ) ≡ n p − 1 2 ( m o d p ) (\frac np)\equiv n^{\frac {p-1}2} (mod\ p) (pn)≡n2p−1(mod p)
p 的二次剩余和二次非剩余的个数均为 p − 1 2 \frac {p−1}2 2p−1（不考虑0）的情况下
1、先用判定式，判别式是否二次剩余，不是就返回-1 2、然后随机找一个a，使得 a 2 − x a^2-x a2−x是模p的二次非剩余 3、设 w ≡ a 2 − x ( m o d p ) w\equiv a^2-x (mod\ p) w≡a2−x(mod p)，则 x ≡ ( a + w ) p + 1 2 x\equiv(a+\sqrt w)^{\frac {p+1}2} x≡(a+w )2p+1就是二次同余方程的解
需要保证调用函数 solve(n,p) 的数是正整数
mt19937_64 gen(time(0)); ll w; struct T { ll x,y; }; T mul(T a,T b,ll p) { T ans; ans.x=(a.x*b.x%p+a.y*b.y%p*w%p)%p; ans.y=(a.x*b.y%p+a.y*b.x%p)%p; return ans; } T qpow2(T base,ll n,ll mod) { T ret={1,0}; while(n) { if(n&1) ret=mul(ret,base,mod); n>>=1; base=mul(base,base,mod); } return ret; } ll qpow(ll base,ll n,ll mod) { ll ret=1; base%=mod; while(n) { if(n&1) ret=ret*base%mod; n>>=1; base=base*base%mod; } return ret; } ll Legendre(ll n,ll p) { return qpow(n,(p-1)>>1,p); } ll solve(ll n,ll p) { if (n==0) return 0; if (n==1) return 1; if(Legendre(n,p)+1==p) return -1; ll a; while(1) { a=gen()%p; w=((a*a-n)%p+p)%p; if(Legendre(w,p)+1==p) break; } T tmp={a,1}; T ans=qpow2(tmp,(p+1)>>1,p); return ans.x; }链接：https://ac.nowcoder.com/acm/contest/889/B
题意：给出 b、c 的值，求 x 、y 的解，如果不存在则输出 -1 -1 ( x + y ) ≡ b ( m o d p ) (x+y) \equiv b (\mod p) (x+y)≡b(modp) x y ≡ c ( m o d p ) xy\equiv c (\mod p) xy≡c(modp)
#include <bits/stdc++.h> #define ll long long using namespace std; const int mod=1e9+7; mt19937_64 gen(time(0)); ll w; struct T { ll x,y; }; T mul(T a,T b,ll p) { T ans; ans.x=(a.x*b.x%p+a.y*b.y%p*w%p)%p; ans.y=(a.x*b.y%p+a.y*b.x%p)%p; return ans; } T qpow2(T base,ll n,ll mod) { T ret={1,0}; while(n) { if(n&1) ret=mul(ret,base,mod); n>>=1; base=mul(base,base,mod); } return ret; } ll qpow(ll base,ll n,ll mod) { ll ret=1; base%=mod; while(n) { if(n&1) ret=ret*base%mod; n>>=1; base=base*base%mod; } return ret; } ll Legendre(ll n,ll p) { return qpow(n,(p-1)>>1,p); } ll solve(ll n,ll p) { if (n==0) return 0; if (n==1) return 1; if(Legendre(n,p)+1==p) return -1; ll a; while(1) { a=gen()%p; w=((a*a-n)%p+p)%p; if(Legendre(w,p)+1==p) break; } T tmp={a,1}; T ans=qpow2(tmp,(p+1)>>1,p); return ans.x; } ll t,b,c; int inv2=qpow(2,mod-2,mod); int main() { scanf("%lld",&t); while(t--) { scanf("%lld%lld",&b,&c); ll res=b*b%mod-4*c%mod; res=(res+mod)%mod; res=solve(res,mod); if(res==-1) { puts("-1 -1"); continue; } ll x=(b-res)*inv2%mod,y=(b+res)*inv2%mod; x=(x+mod)%mod; if(x>y) swap(x,y); printf("%lld %lld\n",x,y); } return 0; }