二次剩余定理及Cipolla算法入门到自闭

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

二次剩余定义：

在维基百科中，是这样说的：如果q等于一个数的平方模 n，则q为模 n 意义下的二次剩余。例如：x ² ≡n(mod p)。否则，则q为模n意义下的二次非剩余。

Cipolla算法： 一个解决二次剩余强有力的工具，用来求得上式的x的一个算法。

需要学习的数论及数学基础： 勒让德符号 、 欧拉判别准则 和 复数运算 。

勒让德符号： 判断n是否为p的二次剩余，p为奇质数。

欧拉定理为x ^φ ⁽ ^p ⁾ ≡1(mod p)

当p为素数时，可知φ(p)=p-1，转化为x ^p-1 ≡1(mod p)

开根号后为 x ⁽ ^p ⁻ ^1)/ ² ≡±1(mod p)，如果等于1就肯定开的了方，为-1一定开不了。所以x是否为n的二次剩余就用这个欧拉判别准则。

qpow(n,(mod-)>>)==mod-

随机找数a ,使得a ² −n为复数的虚数单位的平方，即

随机一个数a，然后对a ² −n进行开方操作（就是计算他勒让德符号的值），直到他们的勒让德符号为-1为止（就是开不了方为止）。就是找到一个a满足(a ² −n) ⁽ ^p ⁻ ^1)/ ² =−1。

    LL a=;

    while(qpow((a*a-n+mod)%mod,(mod-)>>)!=mod-)  a=rand()%mod;

建立复数乘法运算 （(a+bi)(c+di)=(ac+bd*(-1))+(bc+ad)i）

建立一个类似的域，前面寻找了一个a使 (a ² −n) ⁽ ^p ⁻ ^1)/ ² =−1 ，所以我们定义ω=√(a2−n)。那么现在的ω也像i一样，满足ω ² =a ² −n=-1

node two(node a,node b)//复数相乘

{

    node ans;

    ans.x=(a.x*b.x%mod+a.y*b.y%mod*w%mod)%mod;

    ans.y=(a.x*b.y%mod+a.y*b.x%mod)%mod;

    return ans;

}

答案 =(a+ω) ^(p+1)/2

根据拉格朗日定理，可以得出虚数处的系数一定为0。

 node q_pow(node a,LL b){

     node res;

     res.x=,res.y=;

     while(b){

         if(b&)res=two(res,a);

         a=two(a,a);

         b>>=;

     }

     return res;

 }

     node p;

     p.x=a,p.y=,w=(a*a-n+mod)%mod;

     node ans=q_pow(p,(mod+)>>);

     return ans.x;

2019牛客多校训练营第九场B题为Cipolla算法模板题

 #include<bits/stdc++.h>

 #define LL long long

 using namespace std;

 const LL mod=1e9+;

 struct node

 {

     LL x,y;

 };

 LL w;

 node two(node a,node b)//复数相乘

 {

     node ans;

     ans.x=(a.x*b.x%mod+a.y*b.y%mod*w%mod)%mod;

     ans.y=(a.x*b.y%mod+a.y*b.x%mod)%mod;

     return ans;

 }

 node q_pow(node a,LL b)

 {

     node res;

     res.x=,res.y=;

     while(b)

     {

         if(b&)

             res=two(res,a);

         a=two(a,a);

         b>>=;

     }

     return res;

 }

 LL qpow(LL a,LL b)

 {

     LL ans=;

     a%=mod;

     while(b)

     {

         if(b&)

             ans=ans*a%mod;

         a=a*a%mod,b>>=;

     }

     return ans;

 }

 LL solve(LL n)

 {

     if(qpow(n,(mod-)>>)==mod-)//勒让德符号

         return -;

     else if(n==)

         return ;

     LL a=;//找随机a

     while(qpow((a*a-n+mod)%mod,(mod-)>>)!=mod-)//勒让德符号

         a=rand()%mod;

     node p;

     p.x=a,p.y=,w=(a*a-n+mod)%mod;

     node ans=q_pow(p,(mod+)>>);//求出答案

     return ans.x;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     LL q,b,n,x,y,c,t=qpow(,mod-);

     while(T--)

     {

         scanf("%lld%lld",&b,&c);

         q=(b*b-*c+mod)%mod;

         n=solve(q);

         if(n==-)

         {

             printf("-1 -1\n");

             continue;

         }

         x=((b+n)%mod)*t%mod,y=(b-x+mod)%mod;

         if(x>y)

             swap(x,y);

         printf("%lld %lld\n",x,y);

     }

     return ;

 }