• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【洛谷5491】【模板】二次剩余

开发技术 开发技术 2周前 (04-06) 8次浏览

点此看题面

  • 给定(n,p),求所有(xin[0,p))满足(x^2equiv n(mod p))
  • 数据组数(le10^5)(n,ple10^9+9),保证(p)是奇素数

基本引理

(p)意义下,(0)满足恰有一个根(0),一共有(frac{p-1}2)个数(n)满足(x^2equiv n)有两个根(x_1,x_2)(x_1+x_2equiv0(mod p))

非常显然,但又非常重要。

勒让德符号

定义勒让德符号((frac np)),分下列三种取值:

  • (n=0),则((frac np)=0)
  • (n)在模(p)意义下是二次剩余,则((frac np)=1)
  • (n)在模(p)意义下非二次剩余,则((frac np)=-1)

欧拉准则: ((frac np)equiv n^{frac{p-1}2}(mod p))

考虑它的证明,(n=0)时显然满足结论。

否则,因为(p)是奇素数,所以根据费马小定理有(n^{p-1}equiv1(mod p))

而根据二次探测定理,便有(n^{frac{p-1}2}equivpm1(mod p))

如果(n)是二次剩余,则至少有一根(x),那么(n^{frac{p-1}2}equiv x^{2times frac{p-1}2}equiv x^{p-1}equiv1(mod p))

而若(n)非二次剩余,那么(n^{frac{p-2}2})就只能等于(-1)了。

应该还是非常显然的。

二次剩余的求解

我们去寻找一个(a),满足(omega=a^2-n)不是模(p)意义下的二次剩余。(由于模(p)意义下有一半的数都不是二次剩余,只要随机去找,概率应该还是比较高的)

先给出结论,(x=(a+sqrtomega)^{frac{p+1}2})(x^2equiv n(mod p))的一个根。

那么也就是要证明(x^2=(a+sqrt omega)^{p+1}equiv n(mod p))

首先考虑((a+sqrtomega)^p)的展开,根据二项式定理+卢卡斯定理得到它其实就等于(a^p+sqrtomega^p)

根据费马小定理,(a^pequiv a(mod p))

而根据前面勒让德符号中的结论,(sqrtomega^{p-1}=omega^{frac{p-1}2}equiv-1(mod p)),因此(sqrtomega^pequiv-sqrtomega(mod p))

所以得到((a+sqrtomega)^{p+1}equiv(a-sqrtomega)(a+sqrtomega)equiv a^2-omegaequiv n(mod p))

具体实现中只要把(sqrtomega)当作一个虚数,在复数域上求解即可。

注意尽管这样只求出了一个根(x_1),但根据先前的结论,另一个根(x_2=p-x_1)

代码:(O(Tlogp))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
using namespace std;
int n,w,X;struct node
{
	int x,y;I node(CI a=0,CI b=0):x(a),y(b){}//定义一个复数x+y√ω
	I node operator + (Con node& o) {return node((x+o.x)%X,(y+o.y)%X);}
	I node operator - (Con node& o) {return node((x-o.x+X)%X,(y-o.y+X)%X);}
	I node operator * (Con node& o) {return node((1LL*x*o.x+1LL*y*o.y%X*w)%X,(1LL*x*o.y+1LL*y*o.x)%X);}
};
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
I node QP(node x,RI y) {node t=1;W(y) y&1&&(t=t*x,0),x=x*x,y>>=1;return t;}
I int Solve(CI n)//求解二次剩余
{
	if(QP(n,X-1>>1)==X-1) return -1;//如果没有二次剩余
	RI a;W(true) if(a=(1LL*rand()*rand()%X),w=((1LL*a*a-n)%X+X)%X,QP(w,X-1>>1)==X-1) break;//随机一个a满足ω=a^2-n非二次剩余
	return QP(node(a,1),X+1>>1).x;//(a+ω)^((p+1)/2)是一个根
}
int main()
{
	srand(324682339);RI Tt,t;scanf("%d",&Tt);W(Tt--)
	{
		if(scanf("%d%d",&n,&X),!n) {puts("0");continue;}//特判0
		(t=Solve(n))==-1?puts("Hola!"):(t>X-t&&(t=X-t),printf("%d %dn",t,X-t));//有根则必有两根
	}return 0;
}

程序员灯塔
转载请注明原文链接:【洛谷5491】【模板】二次剩余
喜欢 (0)