From 376a77de38a4b552200734bb3c721f0fd01dfc72 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Fri, 24 Feb 2017 11:01:57 +0100 Subject: Lot's of small changes to math chapter. --- math/legendre.cpp | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) create mode 100644 math/legendre.cpp (limited to 'math/legendre.cpp') diff --git a/math/legendre.cpp b/math/legendre.cpp new file mode 100644 index 0000000..adfd3c6 --- /dev/null +++ b/math/legendre.cpp @@ -0,0 +1,17 @@ +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; + } +} -- cgit v1.2.3