BSGS&二次剩余_牛客博客

BSGS

$a^x\equiv b \; (mod \; p) ,p \in prime ,gcd(a,p)=1$

const int MOD=76543;
ll hs[MOD],head[MOD],nxt[MOD],id[MOD],top;
void insert(ll x,int y){
    ll k=x%MOD;
    hs[++top]=x,id[top]=y,nxt[top]=head[k],head[k]=top;
}
ll find(int x){
    ll k=x%MOD;
    for(int i=head[k];i!=-1;i=nxt[i])
    if(hs[i]==x)return id[i];
    return -1;
}
ll bsgs(ll a,ll b,ll n) { //a^x=b mod n
    a%=n,b%=n; //取最小
    if(!a)return -1;
    if(b==1)return 0;
    me(head,-1);top=0;
    int m=sqrt(1.0*n),j;
    ll x=1,p=1,i;
    for(i=0;i<m;i++,p=p*a%n)insert(p*b%n,i);
    for(i=m;;i+=m){
    if((j=find(x=x*p%n))!=-1) return i-j;
    if(i>n) break;
    }
    return -1;
}

EXBSGS

$a^x\equiv b \; (mod \; p) ,p \in N^+ ,gcd(a,p)>=1$

void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
const int mod=100003;
struct node{
    int nxt[mod],val[mod],id[mod],cnt,hd[mod];
    void init(){me(nxt,0),me(val,0),me(id,0),me(hd,0),cnt=0;}
    void insert(ll x,int d){
        int st=x%mod;
        for(int i=hd[st];i;i=nxt[i]){if(val[i]==x)return;}
        val[++cnt]=x,nxt[cnt]=hd[st],id[cnt]=d,hd[st]=cnt;
    }
    int find(ll x){
        int st=x%mod;
        for(int i=hd[st];i;i=nxt[i])if(val[i]==x) return id[i]; 
        return -233;
    }
}ha;
int BSGS(ll a,ll b,ll c){ //a^x=b mod c
    int up=(int)floor(sqrt(1.0*c-1))+1;
    ll ni=0,yy=0;
    exgcd(ksm(a,up,c),c,ni,yy);
    ni=(ni%c+c)%c;//warning!!! 必须变成正数 
    ll kk=1;
    for(int i=0;i<=up-1;i++){
        ha.insert(kk,i);
        kk=(kk*a)%c;
    }
    ll bb=b;
    for(int i=0;i<=up;i++){
        int kk=ha.find(bb);
        if(kk>=0) return i*up+kk;
        bb=(bb*ni)%c;//不断找逆元 递推就可以 
    }
    return -233;
}
int EXBSGS(ll A,ll B,ll C){// A^x=B mod C
    int num=0,yC=C,yB=B,yA=A;
    ll ji=1;int ret=-233;bool flag=false;    
    while(true){
        int g=__gcd(A,C);
        if(g==1) break;
        if(B%g){flag=true;break;}
        B/=g,C/=g,ji=(ji*A/g)%C;
        num++;
    }
    for(int i=0;i<=num;i++){
        ll kk=ksm(yA,i,yC);
        if(kk%yC==yB) return i;
    }
    if(!flag){
        ll ni,yy;
        exgcd(ji,C,ni,yy);
        ni=(ni%C+C)%C;//warning!!! 必须变成正数 
        ll NB=(B*ni)%C;
        ret=BSGS(A,NB,C);
    }
    if(ret>=0) return ret+num;return -233;
}

二次剩余

$x^2 \equiv n \; (mod \; p),p奇素数$

原理： $随机一个数 a ,w=a^2-n 且 ( \frac{w}{p} )=-1 ,x \equiv (a+\sqrt w)^{\frac{p+1}{2}} \; (mod \;p)$

#define random(a,b) (rand()%(b-a+1)+a)
struct node{ll x,y;};
ll p,w;
node operator *(node a,node b){
	node 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;
}
node operator^(node a,ll b){
	node ans={1,0};
	for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;
	return ans;
}
ll legender(ll a){
	ll ans=ksm(a,p-1>>1,p);
	if(ans+1==p)return -1;
	return ans;
}
ll sovle(ll n){
	ll a;
	if(p==2)return n;
	if(legender(n)==-1)return -1;
	srand((unsigned)time(NULL));
    while(true){
		a=random(0,p-1);
		w=(a*a%p-n+p)%p;
		if(legender(w)==-1)break;
	}
	node res={a,1};// a+sqrt(w) 
	res=res^(p+1>>1);
	return res.x;
}
int main(){
    ll n;
    cin>>p>>n;
    n%=p;
    ll ans=sovle(n);
    if(ans==-1)return o("No Solution");
    ll res=p-ans;
    if(res>ans)swap(res,ans);
    if(ans*2!=p)cout<<res<<" ";
    o(ans);
}