我不曾迷路过，不过是跌倒后再次爬起。
总感觉自己已经学过了甚至还有交题记录但是就是没有笔记。
二次剩余
如果存在 ，那么 是 的二次剩余。
并不是所有 都有二次剩余，这里我们着重了解有关 是奇质数的情况（ 相信大家都会）。
勒让德符号
我们定义符号 表示勒让德符号，其具体定义如下：
- 若 是 的二次剩余且， ，则 ；
- 若 不是 的倍数，且 是 的非二次剩余，那么 ；
- 若 ，则 。
然后我们万能的欧拉得到了一个至关重要的准则，称为欧拉判别准则：
Cipolla算法
算法仅能计算当 是奇质数的情况。那么根据欧拉判别准则，有 个数是模 意义下的非二次剩余。
有了上述暴论，我们随机出一个 使得 是 的非二次剩余，成功率大概是 。
然后我们定义 。但问题是 都不是二次剩余哪来的 ？
然后我们打开脑洞，刚刚的所有讨论都是实数范围内，那如果我们把数域扩充到复数，当然会得到不同的结果。
所以我们定义复数域下的 为二次剩余，并用 表示，其中 为模 意义下的数，意义同于实部虚部。
首先有 ，这个证明较为容易：
然后考虑另外一个结论 ，这个证明也是比较容易的。考虑左式二项式展开，因为 是质数，所以对于 一定能被 整除。所以最后只剩下了 。约下来就是右式了。
于是我们得到了一个较为重要的结论：。有了上面的引理，这个证明也十分简单了：
所以我们解出了两个二次剩余解，为 。
但你发现 是个复数啊，这个解不应该也在复数域吗。显然是，但是通过证明， 的虚部为 。证明读者可自行阅读。
至于实现，像 那样写个复数即可，时间复杂度 ，这个是快速幂的 ，当然如果你霉到极致一直找不到 那没办法，但这种一般不可能。
参考实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| int Test;
std::mt19937 rnd((ll)new char);
ll N,Mod,w;
struct Complex
{
ll x,y;
Complex(ll x=0,ll y=0):x(x),y(y){}
friend Complex operator+(Complex &a,Complex &b)
{ return Complex((a.x+b.x)%Mod,(a.y+b.y)%Mod); }
friend Complex operator*(Complex &a,Complex &b)
{ return Complex(((a.x*b.x)%Mod+(a.y*b.y%Mod*w%Mod)%Mod+Mod)%Mod,((a.x*b.y)%Mod+(a.y*b.x)%Mod+Mod)%Mod); }
};
inline ll qPow(ll a,int b)
{
ll res=1;
for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
return res;
}
inline ll qPow(Complex a,int b)
{
Complex res(1,0);
for(;b;b>>=1,a=a*a) (b&1)&&(res=res*a,1);
return res.x%Mod;
}
inline ll Cipolla(ll n,ll p)
{
n%=p;
if(qPow(n,(p-1)/2)==p-1) return -1;
ll a;
while(true)
{
a=rnd()%p;
w=(((a*a)%Mod-n)%Mod+Mod)%Mod;
if(qPow(w,(p-1)/2)==p-1) break;
}
Complex x(a,1);
return qPow(x,(p+1)/2);
}
int main()
{
read(Test);
while(Test--)
{
read(N,Mod);
if(!N){ puts("0");continue; }
ll ret=Cipolla(N,Mod);
if(ret==-1) puts("Hola!");
else
{
ll res=-ret+Mod;
if(ret>res) std::swap(ret,res);
if(ret==res) write(ret,'\n');
else write(ret,' ',res,'\n');
}
}
return 0;
}
|