Function leg

code/mathematics/tonelli_shanks.cpp:2–5

#include "mod_pow.cpp"
ll leg(ll a, ll p) {
  if (a % p == 0) return 0;
  if (p == 2) return 1;
  return mod_pow(a, (p-1)/2, p) == 1 ? 1 : -1; }
ll tonelli_shanks(ll n, ll p) {
  assert(leg(n,p) == 1);
  if (p == 2) return 1;