From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/legendre.cpp | 19 +++---------------- 1 file changed, 3 insertions(+), 16 deletions(-) (limited to 'math/legendre.cpp') diff --git a/math/legendre.cpp b/math/legendre.cpp index adfd3c6..f08755f 100644 --- a/math/legendre.cpp +++ b/math/legendre.cpp @@ -1,17 +1,4 @@ -int legendre(ll a, ll p) { - a %= p; - if (a == 0) return 0; - if (a == 1 || p == 2) return 1; - if (a == 2) return (((p * p - 1) / 8) & 1) ? -1 : 1; - if (isPrime(a)) { - return legendre(p, a) * ((((p - 1) * (a - 1) / 4) & 1) ? -1 : 1); - } else { - map facts; - factor(a, facts); - int res = 1; - for (auto f : facts) - if (f.second & 1) - res *= legendre(f.first, p); - return res; - } +ll legendre(ll a, ll p) { + ll s = powMod(a, p / 2, p); + return s < 2 ? s : -1ll; } -- cgit v1.2.3