二次剩余【模下开方】奇波拉算法

奇波拉算法只适合模数为奇质数的情况

本博客仅提供主干结论和步骤，无繁琐证明

只需掌握  1欧拉判别准则 2重载复数域 3快速幂 4随机数  即可

详细证明链接登录 - 洛谷

欧拉判别准则

判断一个数n是否为模数p的二次剩余（是否能在模p意义下开方)

根据费马小定理

勒德让函数

随机找一个数a, 计算a^2-n函数值。直到勒德让函数值为-1，否则一直寻找。

这里有一个定理为使得勒德让函数为-1的a期望为2，也就是我们平均找两次随机数就够了

重载复数域

复数域中，有一个i,i^2=1。这里我们重新创建一个负数域，令 i^2=  a^2-n

inline complex operator * (complex x, complex y)
 {
	return complex((x.real * y.real + II* x.imag % mod * y.imag) % mod,
 
			(x.imag * y.real + x.real * y.imag) % mod);
}

 其中II指的是i^2,和复数运算一样，只不过把-1换成了II

然后我们这样做的好处是，再写复数时，虚部只需要写系数就够了

最终答案是

也就是计算复数快速幂  (a,1) 1代表i的系数

最终虚数部系数一定为0，所以可以直接输出实部

# include
using namespace std;
typedef long long int ll;
 
ll II,mod;
 
struct cp
{
    ll real,imag;
 
};
 
 
cp operator *(cp x,cp y)
{
    cp z;
 
    z.real=(x.real*y.real%mod+II*x.imag%mod*y.imag%mod)%mod;
 
    z.imag=(x.real*y.imag%mod+x.imag*y.real%mod)%mod;
 
    return z;
}
 
ll qp(ll base, ll pow)
{
    ll ans=1ll;
 
    while(pow)
    {
        if(pow&1)
            ans=ans*base%mod;
 
        base=base*base%mod;
 
        pow>>=1;
 
    }
    return ans;
}
bool check(ll x, ll y)
{
    return qp(x,y)==1;
 
}
 
void  getans(cp base,ll pow,ll &x1,ll&x2)
{
    cp ans;
    ans.real=1ll;
    ans.imag=0;
 
    while(pow)
    {
        if(pow&1)
            ans=ans*base;
 
        pow>>=1;
 
 
        base=base*base;
 
    }
 
    x1=ans.real;
 
    x2=(mod-x1)%mod;
 
 
}
int main ()
{
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
        ll n;
 
        cin>>n;
 
 
        cin>>mod;
 
        if(!n)
        {
            cout<<0<<'\n';
            continue;
 
        }
        if(!check(n,(mod-1)/2))
        {
            cout<<"Hola!"<<'\n';
            continue;
 
        }
 
        ll a=rand()%mod;
 
        while(!a || check((a*a-n+mod)%mod,(mod-1)/2))
            a=rand()%mod;
 
        II=(a*a+ mod-n )%mod;
 
        ll x1,x2;
 
        cp now;
        now.real=a;
 
        now.imag=1ll;
 
 
        getans(now,(mod+1)/2,x1,x2);
 
       if(x1!=x2)
       {
           cout<" "<'\n';
 
       }
       else
       {
           cout<'\n';
       }
 
 
    }
 
    return 0;
 
}