繰り返し二乗法 / 二分累乗法 / バイナリ法
(include/emthrm/math/mod_pow.hpp)

• View this file on GitHub
• Last update: 2022-12-16 05:33:31+09:00
• Include: #include "emthrm/math/mod_pow.hpp"

累乗を高速に求めるアルゴリズムである。

時間計算量

$O(\log{N})$

仕様

名前	戻り値
long long mod_pow(long long x, long long n, const int m);	$x^n \bmod{m}$

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.114-116，マイナビ出版（2012）

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/NTL_1_B/review/4088294/emthrm/C++14

Required by

• $i^k \bmod m$ ($0 \leq i \leq n$) (include/emthrm/math/enumerate_k-th_power.hpp)
• 原始根 (primitive root) 判定 (include/emthrm/math/is_primitive_root.hpp)
• 離散対数問題 (discrete logarithm problem) (include/emthrm/math/mod_log.hpp)
• 平方剰余 (quadratic residue) (include/emthrm/math/mod_sqrt.hpp)

Verified with

• 数学/$i^k \bmod m$ ($0 \leq i \leq n$) (test/math/enumerate_k-th_power.test.cpp)
• 数学/形式的冪級数/形式的冪級数（平方根） (test/math/formal_power_series/formal_power_series.6.test.cpp)
• 数学/原始根判定 (test/math/is_primitive_root.test.cpp)
• 数学/離散対数問題 (test/math/mod_log.test.cpp)
• 数学/繰り返し二乗法 (test/math/mod_pow.test.cpp)
• 数学/平方剰余 (test/math/mod_sqrt.test.cpp)

Code

#ifndef EMTHRM_MATH_MOD_POW_HPP_
#define EMTHRM_MATH_MOD_POW_HPP_

namespace emthrm {

long long mod_pow(long long x, long long n, const int m) {
  if ((x %= m) < 0) x += m;
  long long res = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) res = (res * x) % m;
    x = (x * x) % m;
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_MOD_POW_HPP_

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



namespace emthrm {

long long mod_pow(long long x, long long n, const int m) {
  if ((x %= m) < 0) x += m;
  long long res = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) res = (res * x) % m;
    x = (x * x) % m;
  }
  return res;
}

}  // namespace emthrm

Back to top page