URAL 1123 Square Root（计算二次剩余）

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’. Example input output 5 4 17 3 7 2 7 14 31 10007 20011 2 15 No root 3 4 13 18 5382 14629

求解二次剩余的模版题。

#include <cstdio> #include <algorithm> #include <iostream> using namespace std; /********************************* 计算二次剩余模版即x^2 = n(mod)p *********************************/ typedef long long ll; ll tmod; ll mod(ll n,ll p) { ll temp = 1; while(p > 0) { if(p & 1) temp = temp * n % tmod; n = n * n % tmod; p >>= 1; } return temp; } ll pows(ll n) { ll i; ll temp = 1; for(i = 0; i < n; i++) temp *= 2; return temp; } int main() { int n,p,cs; ll z,q,s,c; ll r,t,m,b,i; ll minx; scanf("%d",&cs); while(cs--) { scanf("%d%d",&n,&p); //p=2时特判 if(p == 2) { if(n % p == 1)printf("1\n"); else printf("No root\n"); continue; } //如果无解 tmod = p; if(mod(n,(p - 1) / 2) != 1) { printf("No root\n"); continue; } q = p - 1; s = 0; while(q % 2 == 0) { q /= 2; s ++; } if(s == 1) { r = mod(n,(p + 1) / 4); } else { while(1) { z = 1 + rand() % (p - 1); if(mod(z,(p - 1) / 2) == (p - 1)) break; } c = mod(z,q); r = mod(n,(1 + q) / 2); t = mod(n,q); m = s; while(1) { if(t % p == 1) break; for(i = 1; i < m; i++) { if(mod(t,pows(i)) == 1) break; } b = mod(c, pows(m - i - 1)); r = r * b % p; t = t * b * b % p; c = b * b % p; m = i; } } r = (r % p + p) % p; //如果只有一个 if(r == p - r)cout<<r<<endl; //如果有两个按照升序输出 else { minx = min(r,p - r); cout<<minx<<" "<<(p - minx)<<endl; } } return 0; }