数学/繰り返し二乗法
(test/math/mod_pow.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B

Depends on

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

Code

/*
 * @title 数学/繰り返し二乗法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B
 */

#include <iostream>

#include "emthrm/math/mod_pow.hpp"

int main() {
  int m, n;
  std::cin >> m >> n;
  std::cout << emthrm::mod_pow(m, n, 1000000007) << '\n';
  return 0;
}

#line 1 "test/math/mod_pow.test.cpp"
/*
 * @title 数学/繰り返し二乗法
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B
 */

#include <iostream>

#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


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

int main() {
  int m, n;
  std::cin >> m >> n;
  std::cout << emthrm::mod_pow(m, n, 1000000007) << '\n';
  return 0;
}

Back to top page