結果
問題 | No.984 Inversion |
ユーザー |
![]() |
提出日時 | 2020-02-11 15:18:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 3,988 bytes |
コンパイル時間 | 958 ms |
コンパイル使用メモリ | 95,184 KB |
最終ジャッジ日時 | 2025-01-08 23:39:02 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
コンパイルメッセージ
main.cpp: In function ‘void n91::main_()’: main.cpp:161:22: warning: ‘ord’ may be used uninitialized [-Wmaybe-uninitialized] 161 | std::cout << ((ord ^ 1) & ((p - 1) / ord) & 1) << std::endl; | ~~~~~^~~~ main.cpp:154:7: note: ‘ord’ was declared here 154 | u64 ord; | ^~~
ソースコード
//#define NDEBUG#include <algorithm>#include <cstddef>#include <cstdint>#include <iostream>#include <utility>#include <vector>namespace n91 {using i8 = std::int_fast8_t;using i32 = std::int_fast32_t;using i64 = std::int_fast64_t;using u8 = std::uint_fast8_t;using u32 = std::uint_fast32_t;using u64 = std::uint_fast64_t;using isize = std::ptrdiff_t;using usize = std::size_t;struct rep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { ++i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr rep(const usize f, const usize l) noexcept: f(std::min(f, l)), l(l) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};struct revrep {struct itr {usize i;constexpr itr(const usize i) noexcept : i(i) {}void operator++() noexcept { --i; }constexpr usize operator*() const noexcept { return i; }constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }};const itr f, l;constexpr revrep(const usize f, const usize l) noexcept: f(l - 1), l(std::min(f, l) - 1) {}constexpr auto begin() const noexcept { return f; }constexpr auto end() const noexcept { return l; }};template <class T> auto md_vec(const usize n, const T &value) {return std::vector<T>(n, value);}template <class... Args> auto md_vec(const usize n, Args... args) {return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));}template <class T> constexpr T difference(const T &a, const T &b) noexcept {return a < b ? b - a : a - b;}template <class T> void chmin(T &a, const T &b) noexcept {if (b < a)a = b;}template <class T> void chmax(T &a, const T &b) noexcept {if (a < b)a = b;}template <class F> class fix_point : private F {public:explicit constexpr fix_point(F &&f) : F(std::forward<F>(f)) {}template <class... Args>constexpr decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, std::forward<Args>(args)...);}};template <class F> constexpr decltype(auto) make_fix(F &&f) {return fix_point<F>(std::forward<F>(f));}template <class T> T scan() {T ret;std::cin >> ret;return ret;}} // namespace n91#include <utility>namespace n91 {template <class T> constexpr T gcd(T m, T n) noexcept {while (n != static_cast<T>(0)) {m %= n;std::swap(m, n);}return m;}template <class T> constexpr T lcm(const T &m, const T &n) noexcept {return m / gcd(m, n) * n;}} // namespace n91#include <algorithm>#include <utility>#include <vector>namespace n91 {template <class T> std::vector<T> divisors(const T &n) {std::vector<T> ret;T i = static_cast<T>(1);while (i * i < n) {if (n % i == static_cast<T>(0)) {ret.push_back(i);ret.push_back(n / i);}++i;}if (i * i == n) {ret.push_back(i);}std::sort(ret.begin(), ret.end());ret.shrink_to_fit();return std::move(ret);}} // namespace n91#include <functional>#include <utility>namespace n91 {template <class T, class U, class Operate = std::multiplies<T>>constexpr T power(T base, U exp, const Operate &oper = Operate(), T iden = 1) {while (exp != 0) {if (exp % 2 != 0) {iden = oper(iden, base);}exp /= 2;base = oper(base, base);}return iden;}} // namespace n91namespace n91 {void main_() {/*std::ios::sync_with_stdio(false);std::cin.tie(nullptr);//*/const u64 p = scan<u64>();const u64 n = scan<u64>();u64 ord;for (const u64 d : divisors(p - 1)) {if (power(n, d, [&](u64 a, u64 b) { return a * b % p; }) == 1) {ord = d;break;}}std::cout << ((ord ^ 1) & ((p - 1) / ord) & 1) << std::endl;}} // namespace n91int main() {n91::main_();return 0;}