2020-2021:teams:legal_string:lgwza:二次剩余
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:二次剩余 [2021/01/17 20:42] lgwza 创建 |
2020-2021:teams:legal_string:lgwza:二次剩余 [2021/01/17 20:48] (当前版本) lgwza [例题] |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| $$ | $$ | ||
| 通俗一些，可以认为是求模意义下的开方。这里只讨论 **$p$ 为奇素数** 的求解方法，将会使用 Cipolla 算法。 | 通俗一些，可以认为是求模意义下的开方。这里只讨论 **$p$ 为奇素数** 的求解方法，将会使用 Cipolla 算法。 | ||
| + | |||
| + | ===== 解的数量 ===== | ||
| + | |||
| + | 对于 $x^2\equiv n\pmod p$，能满足 “$n$ 是模 $p$ 的二次剩余” 的 $n$ 一共有 $\frac{p-1}{2}$ 个（$0$ 不包括在内），二次非剩余有 $\frac{p-1}{2}$ 个。 | ||
| + | |||
| + | 对于给定的 $n$ 和 $p$，若 $n$ 是 $p$ 的二次剩余，则关于 $x$ 的方程 $x^2\equiv n\pmod p$ 有且仅有两个解 $\pm x_0$ 满足 $x_0^2\equiv n\pmod p$。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== 勒让德符号 ===== | ||
| + | |||
| + | $$ | ||
| + | \left(\frac n p\right)=\begin{cases}1,\,&p\nmid n\text{且}n\text{是}p\text{的二次剩余}\\ -1,\,&p\nmid n \text{且}n\text{不是}p\text{的二次剩余}\\ 0,\,&p\mid n\end{cases} | ||
| + | $$ | ||
| + | |||
| + | |||
| + | |||
| + | ===== 欧拉判别准则 ===== | ||
| + | |||
| + | $$ | ||
| + | \left(\frac n p\right)\equiv n^{\frac{p-1}{2}}\pmod p | ||
| + | $$ | ||
| + | |||
| + | $n$ 是二次剩余，当且仅当 $n^{\frac{p-1}{2}}\equiv 1\pmod p$。 | ||
| + | |||
| + | $n$ 是二次非剩余，当且仅当 $n^{\frac{p-1}{2}}\equiv -1\pmod p$。 | ||
| + | |||
| + | |||
| + | |||
| + | ===== Cipolla 算法 ===== | ||
| + | |||
| + | 找到一个数 $a$ 满足 $a^2-n$ 是 **二次非剩余**，至于为什么要找满足二次非剩余的数，在下文会给出解释。这里通过生成随机数再检验的方法来实现，由于二次非剩余的数量为 $\frac{p-1}{2}$，接近 $\frac p 2$，所以期望约 $2$ 次就可以找到这个数。 | ||
| + | |||
| + | 建立一个“复数域”，并不是实际意义上的复数域，而是根据复数域的概念建立的一个类似的域。在复数中 $i^2=-1$，这里定义 $i^2=a^2-n$ ，于是就可以将所有的数表达为 $A+Bi$ 的形式，这里的 $A$ 和 $B$ 都是模意义下的数，类似复数中的实部和虚部。 | ||
| + | |||
| + | 在有了 $i$ 和 $a$ 后可以直接得到答案， $x^2\equiv n\pmod p$ 的解为 $(a+i)^{\frac{p+1}2}$。 | ||
| + | |||
| + | |||
| + | |||
| + | 参考实现： | ||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | |||
| + | typedef long long ll; | ||
| + | int t; | ||
| + | ll n, p; | ||
| + | ll w; | ||
| + | |||
| + | struct num { //建立一个复数域 | ||
| + | ll x, y; | ||
| + | }; | ||
| + | |||
| + | num mul(num a, num b, ll p) { //复数乘法 | ||
| + | num ans = {0, 0}; | ||
| + | ans.x = ((a.x * b.x % p + a.y * b.y % p * w % p) % p + p) % p; | ||
| + | ans.y = ((a.x * b.y % p + a.y * b.x % p) % p + p) % p; | ||
| + | return ans; | ||
| + | } | ||
| + | |||
| + | ll binpow_real(ll a, ll b, ll p) { //实部快速幂 | ||
| + | ll ans = 1; | ||
| + | while (b) { | ||
| + | if (b & 1) ans = ans * a % p; | ||
| + | a = a * a % p; | ||
| + | b >>= 1; | ||
| + | } | ||
| + | return ans % p; | ||
| + | } | ||
| + | |||
| + | ll binpow_imag(num a, ll b, ll p) { //虚部快速幂 | ||
| + | num ans = {1, 0}; | ||
| + | while (b) { | ||
| + | if (b & 1) ans = mul(ans, a, p); | ||
| + | a = mul(a, a, p); | ||
| + | b >>= 1; | ||
| + | } | ||
| + | return ans.x % p; | ||
| + | } | ||
| + | |||
| + | ll cipolla(ll n, ll p) { | ||
| + | n %= p; | ||
| + | if (p == 2) return n; | ||
| + | if (binpow_real(n, (p - 1) / 2, p) == p - 1) return -1; | ||
| + | ll a; | ||
| + | while (1) { //生成随机数再检验找到满足非二次剩余的a | ||
| + | a = rand() % p; | ||
| + | w = ((a * a % p - n) % p + p) % p; | ||
| + | if (binpow_real(w, (p - 1) / 2, p) == p - 1) break; | ||
| + | } | ||
| + | num x = {a, 1}; | ||
| + | return binpow_imag(x, (p + 1) / 2, p); | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | |||
| + | |||
| + | ===== 例题 ===== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P5491|【模板】二次剩余]] | ||
| + | |||
| + | 题意：求解方程 $x^2\equiv N\pmod p$ | ||
| + | |||
| + | 题解：模板题 | ||
| + | |||
| + | 代码： | ||
| + | |||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | ll w; | ||
| + | struct num{ | ||
| + | ll x,y; | ||
| + | }; | ||
| + | num mul(num a,num b,ll p){ | ||
| + | num ans={0,0}; | ||
| + | ans.x=((a.x*b.x%p+a.y*b.y%p*w%p)%p+p)%p; | ||
| + | ans.y=((a.y*b.x%p+a.x*b.y%p)%p+p)%p; | ||
| + | return ans; | ||
| + | } | ||
| + | ll binpow_real(ll a,ll b,ll p){ | ||
| + | ll ans=1; | ||
| + | while(b){ | ||
| + | if(b&1) ans=ans*a%p; | ||
| + | a=a*a%p; | ||
| + | b>>=1; | ||
| + | } | ||
| + | return ans%p; | ||
| + | } | ||
| + | ll binpow_imag(num a,ll b,ll p){ | ||
| + | num ans={1,0}; | ||
| + | while(b){ | ||
| + | if(b&1) ans=mul(ans,a,p); | ||
| + | a=mul(a,a,p); | ||
| + | b>>=1; | ||
| + | } | ||
| + | return ans.x%p; | ||
| + | } | ||
| + | ll cipolla(ll n,ll p){ | ||
| + | n%=p; | ||
| + | if(p==2) return n; | ||
| + | if(binpow_real(n,(p-1)/2,p)==p-1) return -1; | ||
| + | ll a; | ||
| + | while(1){ | ||
| + | a=rand()%p; | ||
| + | w=((a*a%p-n)%p+p)%p; | ||
| + | if(binpow_real(w,(p-1)/2,p)==p-1) break; | ||
| + | } | ||
| + | num x={a,1}; | ||
| + | return binpow_imag(x,(p+1)/2,p); | ||
| + | } | ||
| + | int main(){ | ||
| + | srand(time(0)); | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | while(t--){ | ||
| + | ll n,p; | ||
| + | scanf("%lld %lld",&n,&p); | ||
| + | if(!n){ | ||
| + | puts("0");continue; | ||
| + | } | ||
| + | ll ans1=cipolla(n,p),ans2; | ||
| + | if(ans1==-1){ | ||
| + | puts("Hola!");continue; | ||
| + | } | ||
| + | ans2=p-ans1; | ||
| + | if(ans1==ans2) printf("%lld\n",ans1); | ||
| + | else if(ans1<ans2) printf("%lld %lld\n",ans1,ans2); | ||
| + | else printf("%lld %lld\n",ans2,ans1); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | |||
| + | |||
| + | ===== 参考链接 ===== | ||
| + | |||
| + | [[https://oi-wiki.org/math/quad-residue/|OI Wiki]] | ||
| + | |||
2020-2021/teams/legal_string/lgwza/二次剩余.1610887367.txt.gz · 最后更改: 2021/01/17 20:42 由 lgwza
