1 files changed, 3 insertions, 16 deletions
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<ll, int> 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;
 }