orangejuice's blog
按ctrl会跳搜索,右上角选择day/night mode 似乎修好了搜索
测试中博客
二次剩余(懒人模板总结)
只考虑奇质数的情况
设求√a(modP)
Part1 判断
存在二次剩余即a(P−1)2=1(modP)
(对于所有a=0,1的情况需要特判)
Part2 原根法求二次剩余
先求出P的一个原根g
那么可以用gk表示出[1,P−1]的所有数
用BSGS可以在O(√nlogn)的时间内求出a=gk
如果存在原根,那么kmod2=0
答案就是gk2modP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| int Quad(int a,int k=0) { if(a<=1) return a; int g=Getg(P); static map <int,int> M; int S=sqrt(P-1); for(int i=0,t=1;i<S;++i,t=1ll*t*g%P) M[t]=i; int res=0; int w=qpow(g,S); for(int i=0,t=1;i<P-1;i+=S,t=1ll*t*w%P) { ll x=1ll*a*qpow(t,P-2)%P; if(M.count(x)) { res=M[x]+i; break; } } res=qpow(g,res/2); if(k) res=min(res,(P-res)%P); return res; }
|
Part3 更快的方法
要先找到一个数x,满足不存在√x2−a(modP)
可以随机x,期望可以在O(1)时间内找到这样的x
然后构造复数(α,β)=α+√x2−aβ
求出(x,1)(P+1)2,模拟复数乘法即可
可以证明结果没有虚部,就是答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| int Quad(int a,int k=0) { if(a<=1) return a; ll x; while(1) { x=1ll*rand()*rand()%P; if(qpow((x*x-a+P)%P,(P-1)/2)!=1) break; } ll w=(x*x-a+P)%P; Pii res=mp(1,0),t=mp(x,1); auto Mul=[&](Pii a,Pii b){ int x=(1ll*a.first*b.first+1ll*a.second*b.second%P*w)%P; int y=(1ll*a.first*b.second+1ll*a.second*b.first)%P; return mp(x,y); }; int 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; if(k) r=min(r,(P-r)%P); return r; }
|
本文代表个人观点,内容仅供参考。若有不恰当之处,望不吝赐教!