数学/ヤコビ記号
(test/math/jacobi_symbol.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://yukicoder.me/problems/no/984

Depends on

• ヤコビ記号 (Jacobi symbol) (include/emthrm/math/jacobi_symbol.hpp)

Code

/*
 * @title 数学/ヤコビ記号
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/984
 */

#include <iostream>

#include "emthrm/math/jacobi_symbol.hpp"

int main() {
  int p, n;
  std::cin >> p >> n;
  std::cout << (n > 1 && emthrm::jacobi_symbol(n, p) == -1 ? 1 : 0) << '\n';
  return 0;
}

#line 1 "test/math/jacobi_symbol.test.cpp"
/*
 * @title 数学/ヤコビ記号
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/984
 */

#include <iostream>

#line 1 "include/emthrm/math/jacobi_symbol.hpp"



#include <bit>
#include <cassert>
#include <utility>

namespace emthrm {

int jacobi_symbol(long long a, long long p) {
  assert(p > 0 && p & 1);
  if (p == 1) [[unlikely]] return 1;
  if ((a %= p) < 0) a += p;
  if (a == 0) [[unlikely]] return 0;
  int res = 1;
  while (a > 0) {
    const int p2 = std::countr_zero(static_cast<unsigned long long>(a));
    if ((p2 & 1) && ((p + 2) & 4)) res = -res;
    a >>= p2;
    if (a & p & 2) res = -res;
    std::swap(a, p);
    a %= p;
  }
  return p == 1 ? res : 0;
}

}  // namespace emthrm


#line 10 "test/math/jacobi_symbol.test.cpp"

int main() {
  int p, n;
  std::cin >> p >> n;
  std::cout << (n > 1 && emthrm::jacobi_symbol(n, p) == -1 ? 1 : 0) << '\n';
  return 0;
}

Back to top page