1132. Square RootTime limit: 1.0 second 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 InputOne 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 ≤ OutputFor 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. Sample
|
求x*x=a(mod n) 解x。利用勒让德符号。
题意：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; }