C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @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; }