1132. Square Root
Time limit: 1.0 second
Memory limit: 64 MB
The number
x is called a square root of
a modulo
n (root(
a,
n)) if
x*
x =
a (mod
n). Write the program to find the square root of number
a by given modulo
n.
Input
One number
K in the first line is an amount of tests (
K ≤ 100000). Each next line represents separate test, which contains integers
a and
n (1 ≤
a,
n ≤ 32767,
n is prime,
a and
n are relatively prime).
Output
For each input test the program must evaluate all possible values root(
a,
n) in the range from 1 to
n− 1 and output them in increasing order in one separate line using spaces. If there is no square root for current test, the program must print in separate line: ‘No root’.
Sample
|
题意：x^2=a(mod n)（gcd(a,n)=1,n为素数）（有解x升序输出，无解输出"No root"(不包含双引号)）。
若
是奇质数且不能整除，则：
-
是模
的二次剩余
当且仅当：
-
是模
的非二次剩余当且仅当：
以勒让德符号表示，即为：
费马小定理是数论中的一个定理：假如a是一个整数，p是一个质数，那么是p的倍数，可以表示为
如果a不是p的倍数，这个定理也可以写成
-
- 当n不整除a,n为奇素数时，方程x^2=a(mod n)有解<==>a^((n-1)/2)=1(mod n)，此时a称之为n的二次剩余类。相反无解<==>a^((n-1)/2)=-1(或者用n-1表示)(mod n)（欧拉准则）,此时称a为n的非二次剩余类。
-
#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; long long pow_mod(long long a,long long b,long long p) { long long res=1; while(b>0) { if(b&1)res=(res*a)%p; a=(a*a)%p; b>>=1; } return res; } long long solve(long long a,long long p) { long long q=p-1,s=0; while(q%2==0) { s++; q>>=1; } if(s==1)return pow_mod(a,(p+1)/4,p); long long z; while(1) { z = 1 + rand()%(p - 1); if(pow_mod(z, (p - 1)/2,p) != 1) break; } long long c = pow_mod(z, q , p); long long r = pow_mod(a, (q + 1)/2, p); long long t = pow_mod(a, q, p); long long m = s, b,i; while(1) { if(t%p==1)break; for(i=1; i<m; i++)if(pow_mod(t,1<<i,p)==1)break; b=pow_mod(c,1<<(m-i-1),p); r=(r*b)%p; c=(b*b)%p; t=(t*c)%p; m=i; } return r; } int main() { long long a,p,i; int t; scanf("%d",&t); while(t--) { scanf("%I64d%I64d",&a,&p); if(p==2) { if(a%p==1)printf("1\n"); else printf("No root\n"); continue; } if(pow_mod(a, (p-1)/2,p) != 1) { puts("No root"); continue; } i=solve(a,p); if(p-i==i)printf("%I64d\n",i); else printf("%I64d %I64d\n",min(i,p-i),max(i,p-i)); } return 0; }
