【模板】二次剩余

FxorG · 2021-07-04 18:12:39 · 个人记录

大佬的blog

具体看blog吧，这里只是列出代码需要用到的。

欧拉准则：n^{\frac{p-1}{2}} \equiv 1 与n是二次剩余是等价的。 判定时判这个东西就好了。

定义 i^2 \equiv a^2-n，我们要使得 a^2-n 不是二次剩余。

解为 (a+i)^{\frac{p+1}{2}}。

随机a之后暴力判断即可，这样期望2次就可以找到a。

#include <bits/stdc++.h>

#define int long long

using namespace std;

int mul_i,x0,x1,n,mod;

struct CP {
    int x,y;
    CP(int xx=0,int yy=0) {
        x=xx; y=yy;
    }
    CP operator * (const CP&A) const {
        return CP((x*A.x%mod+y*A.y%mod*mul_i%mod)%mod,(x*A.y%mod+y*A.x%mod)%mod);
    } 
};

CP Ipow(CP x,int y) {
    CP res(1,0);
    while(y) {
        if(y&1) res=res*x;
        x=x*x; y>>=1;
    }
    return res;
}

int fpow(int x,int y) {
    x%=mod; int res=1;
    while(y) {
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod; y>>=1;
    }
    return res;
}

bool check(int x) {
    return fpow(x,(mod-1)>>1)==1;
}

void solve() {
    int a=rand()%mod;
    while(!a||check((a*a+mod-n)%mod)) a=rand()%mod;
//  cout<<a<<endl;
    mul_i=(a*a+mod-n)%mod;
    x0=Ipow(CP(a,1),(mod+1)>>1).x;
    x1=mod-x0;
}

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

signed main() {
    srand(time(0)); 
    srand((rand()*2)*(rand()*3));
    int t;
    t=rd();
    while(t--) {
        n=rd(); mod=rd();
        if(!n) {
            puts("0");
            continue;
        }
        if(!check(n)) {
            puts("Hola!"); 
            continue;
        }
        solve();
        if(x0==x1) printf("%lld\n",x0);
        else if(x0<x1) printf("%lld %lld\n",x0,x1);
        else printf("%lld %lld\n",x1,x0);
    }
}