|  | 
|  | 
| back to board | WA#2 Posted by LNCP  8 Feb 2015 09:50I use Tonelli-Shanks algo,but i got WA#2.By now I had read all te topic but hadn't found the error.Please give me some hints or cases.the key code:
 
 int inverse(int a, int m)//thr inverse element of a(modulo m);
 int quickpower(int a, int n, int m)//a^n(modulo m);
 void sqrt(int a, int p)
 {
 if(p==2)
 {
 cout << 1 << endl;
 return;
 }
 if(quickpower(a,(p-1)/2,p)!=1)
 {
 cout << "No root" << endl;
 return;
 }
 int s, t = 0, b = 0, i, j, x, y, inv, N;
 for (s = p - 1; !(s & 1); s /= 2) t++;
 inv = inverse(a, p);
 x = quickpower(a, (s + 1) / 2, p);
 for (N = 2; quickpower(N, (p - 1) / 2, p) == 1; N++);
 for (i = t - 2; i >= 0; i--)
 {
 b = b ? b*b%p : quickpower(N, s, p);
 y = x*x%p*inv%p;
 for (j = 1; j <= i; j++) y = y*y%p;
 if (y != 1) (x *= b) /= p;
 }
 if (2 * x < p) cout << x << " " << p - x << endl;
 else cout << p - x << " " << x << endl;
 return;
 }
Re: WA#2 Posted by LNCP  8 Feb 2015 09:54I had got AC now.Really a small mistake! | 
 | 
|