Mod pow
(Mylib/Number/Mod/mod_pow.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• mod_pow(n, p, m)
  • $n ^ p \pmod m$を求める。
  • Time complexity $O(\log p)$

Requirements

Notes

Problems

References

Required by

• Binomial coefficient (Mylib/Combinatorics/binomial_coefficient.cpp)
• Convolution (Index multiplication mod P) (Mylib/Convolution/convolution_multiply.cpp)
• Graph vertex coloring (Mylib/Graph/Coloring/chromatic_number.cpp)
• Formal power series (Sqrt) (Mylib/Math/fps_sqrt.cpp)
• Mod logarithm (Mylib/Number/Mod/mod_log.cpp)
• Mod sqrt (Mylib/Number/Mod/mod_sqrt.cpp)
• Primitive root (Mylib/Number/Prime/primitive_root.cpp)

Verified with

• test/aoj/2136/main.test.cpp
• test/aoj/2530/main.test.cpp
• test/yosupo-judge/bernoulli_number/main.test.cpp
• test/yosupo-judge/binomial_coefficient/main.test.cpp
• test/yosupo-judge/chromatic_number/main.test.cpp
• test/yosupo-judge/convolution_mod/main.test.cpp
• test/yosupo-judge/discrete_logarithm_mod/main.test.cpp
• test/yosupo-judge/exp_of_formal_power_series/main.montgomery.test.cpp
• test/yosupo-judge/exp_of_formal_power_series/main.test.cpp
• test/yosupo-judge/inv_of_formal_power_series/main.test.cpp
• test/yosupo-judge/kth_term_of_linearly_recurrent_sequence/main.test.cpp
• test/yosupo-judge/log_of_formal_power_series/main.test.cpp
• test/yosupo-judge/multipoint_evaluation/main.test.cpp
• test/yosupo-judge/partition_function/main.fps.test.cpp
• test/yosupo-judge/polynomial_taylor_shift/main.test.cpp
• test/yosupo-judge/pow_of_formal_power_series/main.test.cpp
• test/yosupo-judge/sharp_p_subset_sum/main.test.cpp
• test/yosupo-judge/sqrt_mod/main.test.cpp
• test/yosupo-judge/sqrt_of_formal_power_series/main.test.cpp
• test/yosupo-judge/stirling_number_of_the_first_kind/main.test.cpp
• test/yosupo-judge/stirling_number_of_the_second_kind/main.test.cpp
• test/yukicoder/931/main.test.cpp

Code

#pragma once
#include <cstdint>

namespace haar_lib {
  constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m) {
    int64_t ret = 1;
    while (p > 0) {
      if (p & 1) (ret *= n) %= m;
      (n *= n) %= m;
      p >>= 1;
    }
    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Mod/mod_pow.cpp"
#include <cstdint>

namespace haar_lib {
  constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m) {
    int64_t ret = 1;
    while (p > 0) {
      if (p & 1) (ret *= n) %= m;
      (n *= n) %= m;
      p >>= 1;
    }
    return ret;
  }
}  // namespace haar_lib

Back to top page