题目链接:http://poj.org/problem?id=1808
题意:如下。对于素数p,若存在x使得x^2%p=a,则其值为1。否则为-1。现在给出a、p,计算其值。
思路:
若a为正数则利用公式1即可;否则利用公式2、5将-1提出来。跟本题有点关系的是计算x^2%p=a最小的x。在最下面给出代码,modsqr(a,p)函数。
i64 mul(i64 a,i64 b,i64 M) { i64 ans=0; a%=M; b%=M; while(b) { if(b&1) ans=(ans+a)%M; a=(a+a)%M; b>>=1; } return ans; } i64 Pow(i64 a,i64 b,i64 M) { i64 ans=1; while(b) { if(b&1) ans=mul(ans,a,M); a=mul(a,a,M); b>>=1; } return ans; } int judge(i64 d,i64 p) { if(d>0) { d%=p; if(d==0) return 0; if(Pow(d,(p-1)/2,p)==1) return 1; return -1; } else { int coef=((p-1)%4==0)?1:-1; d=-d; d%=p; if(Pow(d,(p-1)/2,p)==1) return coef; else return -coef; } } i64 d,p; int main() { int num=0; rush() { scanf("%lld%lld",&d,&p); printf("Scenario #%d:\n",++num); PR(judge(d,p)==-1?-1:1); puts(""); } }
i64 modsqr(i64 a,i64 n) { if(n==2) return a%n; if(Pow(a,(n-1)/2,n)!=1) return -1; i64 x; if(n%4==3) x=Pow(a,(n+1)/4,n); else { i64 b; for(b=1;Pow(b,(n-1)/2,n)==1;b++); i64 i=(n-1)/2,k=0; do { i>>=1; k>>=1; if((Pow(a,i,n)*Pow(b,k,n)+1)%n==0) { k+=(n-1)/2; } }while(i%2==0); x=Pow(a,(i+1)/2,n)*Pow(b,k/2,n)%n; } if(x*2>n) x=n-x; return x; }