【数论】a是模p的二次非剩余？|今日看点

(资料图片仅供参考)

在数论中，特别在同余理论里,一个整数X对另一个整数p的二次剩余（英语：Quadratic residue）指X的平方除以p得到的余数。 当存在某个X，式子 x 2 ≡ a m o d    p x^2\equiv a\mod p x2≡amodp 成立时，称“a是模p的二次剩余” 当对任意不成立时，称“ a是模 p的二次非剩余”。 对于质数2来说，每个整数都是它的二次剩余。 所以讨论的都是奇素数。 通过欧拉判别条件…。 其余知识点来源： click click click 带上一道例题click 题意：裸题二次剩余，给定a,n，求x属于[1，p）。Cipolla解法。

#include#include#include#include#include#include#include#include#include#include#include#include#include#define inf 0x3f3f3f3f#define llinf 0x3f3f3f3f3f3f3f3f#define MAX_len 50100*4using namespace std;typedef long long ll;const int mod=1e9+7;struct A{ll x,y;};ll w;A mul_two(A a,A b,ll p){A 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;}A qpow_two(A a,ll n,ll p){A ans;    ans.x=1;    ans.y=0;    while(n)    {if(n&1)        {ans=mul_two(ans,a,p);        }        n>>=1;        a=mul_two(a,a,p);    }    return ans;}ll quickpow(ll a,ll n, ll p){ll res=1;    while(n)    {if(n&1)        {res=(res*a)%p;        }        a=(a*a)%p;        n>>=1;    }    return res;}ll Legendre(ll a,ll p){return quickpow(a,(p-1)/2,p);}ll solve(ll n,ll p){if(p==2)        return 1;    if(Legendre(n,p)-p==-1)    {return -1;    }    ll a,temp;    while(1)    {a=rand()%p;        temp=a*a-n;        w=(temp%p+p)%p;        if(Legendre(w,p)-p==-1)            break;    }    A tmp;    tmp.x=a;    tmp.y=1;    A ans=qpow_two(tmp,(p+1)/2,p);    return ans.x;}int main(){int T;    scanf("%d",&T);    ll a,p,w;    while(T--)    {scanf("%lld %lld",&a,&p);        ll temp=solve(a,p);        if(temp==-1)        {printf("No root\n");            continue;        }        ll f=abs(temp-p);         if(temp>f)        {swap(temp,f);        }        if(f==temp)        {printf("%lld\n",temp);        }        else            printf("%lld %lld\n",temp,f);    }    return 0;}