ural 1132

题目：http://acm.timus.ru/problem.aspx?space=1&num=1132

很无奈的一个题，看解题报告没看懂怎么回事，问的队友，然后不知道他怎么找的那些资料，然后我就是直接看的链接，

http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm

再加上 n == 2时特判，然后就是 r == n - r 时，输出一个，然后就是按照那个算法步骤算了

View Code

 1 typedef long long ll;
 2 ll tmod;
 3 ll mod(ll n,ll p)
 4 {
 5     ll temp = 1;
 6     while(p > 0)
 7     {
 8         if(p & 1) temp = temp * n % tmod;
 9         n = n * n % tmod;
10         p /= 2;
11     }
12     return temp;
13 }
14 ll pows(ll n)
15 {
16     ll i;
17     ll temp = 1;
18     for(i = 0; i < n; i++)
19     temp *= 2;
20     return temp;
21 }
22 
23 int main()
24 {
25     int n,p,cs;
26     ll z,q,s,c;
27     ll r,t,m,b,i;
28     ll minx;
29     scanf("%d",&cs);
30     while(cs--)
31     {
32         scanf("%d%d",&n,&p);
33         if(p == 2)
34         {
35             if(n % p == 1)printf("1\n");
36             else printf("No root\n");
37             continue;
38         }
39         tmod = p;
40         if(mod(n,(p - 1) / 2) != 1) {printf("No root\n"); continue;}
41         q = p - 1;
42         s = 0;
43         while(q % 2 == 0)
44         {
45             q /= 2;
46             s ++;
47         }
48         if(s == 1)
49         {
50             r = mod(n,(p + 1) / 4);
51         }
52         else
53         {
54             while(1)
55         {
56             z = 1 + rand() % (p - 1);
57             if(mod(z,(p - 1) / 2) == (p - 1)) break;
58         }
59         c = mod(z,q);
60         r = mod(n,(1 + q) / 2);
61         t = mod(n,q);
62         m = s;
63         while(1)
64         {
65             if(t % p == 1) break;
66             for(i = 1; i < m; i++)
67             {
68                 if(mod(t,pows(i)) == 1) break;
69             }
70             b = mod(c, pows(m - i - 1));
71             r = r * b % p;
72             t = t * b * b % p;
73             c = b * b % p;
74             m = i;
75         }
76         }
77         r = (r % p + p) % p;
78         if(r == p - r)cout<<r<<endl;
79         else
80         {
81             minx = Min(r,p - r);
82             cout<<minx<<" "<<(p - minx)<<endl;
83         }
84     }
85     return 0;
86 }