传送门
首先:
勒让德符号:
(pa)=⎩⎪⎨⎪⎧1−10a是%p意义下的二次剩余a是%p意义下的非二次剩余a≡0(%p)
有结论(欧拉准则)
(pa)≡a2p−1
证明
当a≡0(%p)时显然成立
由于费马小定理:ap−1≡1
所以a2p−1≡1 or −1(%p)
首先证明(pa)=1时a2p−1=1
必要性:
由于a≡x2,a2p−1≡(x2)2p−1≡xp−1≡1(%p)
充分性:
设%p意义下原根为g,则gk≡ap−1≡1(%p)
则一定存在gi≡a
则g2i(p−1)=1
又gp−1≡1
所以2∣i
所以必然存在g2i≡x0(%p)
(pa)=−1
反证可以得到xp−1≡−1(%p),显然是不可能的
所以我们可以判断k在%p意义下是否存在二次剩余
Cipolla算法
求解p为奇质数的情况
随机一个数b
使w≡b2−a且不存在二次剩余
由于w在%p不存在二次剩余
可以类似虚数那样设i=w
由于b2−w≡a≡x2
b2−w≡b2−i2≡(b+i)(b−i)
考虑(b+i)p=∑j=0p(jp)bjip−j
由于当j!=0 or p时,(jp)≡0
所以(b+i)p≡bp+ip≡bp−1b+w2p−1i
由于w是%p非二次剩余,所以w2p−1≡−1
所以(b+i)p≡b−i
所以x2≡(b+i)(b−i)≡(b+i)p+1
x≡(b+i)2p+1
由于%p意义下非二次剩余不会少于O(2p)个
所以期望找2次b就存在w是非二次剩余
复杂度O(logp)
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define ll long long
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
int mod,w;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?a+=mod:0;}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b,int res=1){
for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
struct plx{
int x,y;
plx(int _x=1,int _y=0):x(_x),y(_y){}
friend inline plx operator *(cs plx &a,cs plx &b){
return plx(add(mul(a.x,b.x),mul(mul(a.y,b.y),w)),add(mul(a.x,b.y),mul(a.y,b.x)));
}
};
inline plx ksm(plx a,int b){
plx res=plx();
for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
return res;
}
inline int solve(int a){
if(mod==2)return 1;
if(ksm(a,(mod-1)/2)==mod-1)return -1;
int b;
while(1){
b=rand()%mod;
w=dec(mul(b,b),a);
if(ksm(w,(mod-1)/2)==mod-1)break;
}
return ksm(plx(b,1),(mod+1)/2).x;
}
int main(){
int T=read();
srand(time(NULL));
while(T--){
int a=read();mod=read();a%=mod;
a=solve(a);
if(a!=-1){
int b=mod-a;
if(a>b)swap(a,b);
if(a!=b)cout<<a<<" "<<b<<'
';
else cout<<a<<'
';
}
else cout<<"No root
";
}
}