|
|
back to boardWA#2 Posted by LNCP 8 Feb 2015 09:50 I 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:54 I had got AC now.Really a small mistake! |
|
|