首页 > 代码库 > URAL1132_Square Root

URAL1132_Square Root

2024-07-15 10:45:25   214人阅读

求解方程，x^2=n (mod P)。

解二次同余方程的步骤：

1、首先判断勒让德符号(n,p)是否的等于1，即n^((p-1/2)=1 (mod p)是否成立。不成立显然无解。（略）

2、任取0-(p-1)中的一a值，判断w=a*a-n是否是P的二次同余，直到找到一个否定的答案即可。（大约有一半是否定答案）

3、根据找到的w，(a+sqrt(w))^((p+1)/2)就是二次同余的解，同时最多只有两解，且两数之和为P。（要用到二次域，囧rz）

中间有一定量的推导过程，但是不是很难，琢磨琢磨吧。

 

对于这个题目，注意一种特殊情况，p=2时，直接输出1即可。

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>using namespace std;int a,w;int T,n,p,A0,B0;struct twice{    int A,B;    twice() { }    twice(int AA,int BB) { A=AA,B=BB; }    twice operator * ( twice T ) const {        A0=A*T.A+(B*T.B)%p*w;        B0=A*T.B+B*T.A;        return twice(A0%p,B0%p);    }};int power(int A,int B){    int C=1;    while (B){        if (B&1) C=C*A%p;        A=A*A%p,B>>=1;    }    return C;}twice power(twice A,int B){    twice C(1,0);    while (B){        if (B&1) C=C*A;        A=A*A,B>>=1;    }    return C;}bool lgd(int A,int B){    return power(A,(B-1)/2)==1;}int main(){    scanf("%d",&T);    while (T--){        scanf("%d%d",&n,&p);        if (p==2){            puts("1");            continue;        }        if (!lgd(n,p)){            puts("No root");            continue;        }        for (;;){            a=rand()%p;            w=((a*a-n)%p+p)%p;            if (!lgd(w,p)) break;        }        twice T(a,1);        T=power(T,(p+1)/2);        int ans1=(int)T.A,ans2=(int)p-T.A;        if (ans1>ans2) swap(ans1,ans2);        printf("%d %d\n",ans1,ans2);    }    return 0;}

 


联系
我们