modint/mod-pow.hpp

• View this file on GitHub
• Last update: 2025-10-10 17:35:46+09:00
• Include: #include "modint/mod-pow.hpp"

Required by

• fps/fps-sqrt.hpp
• Relaxed (fps/relaxed.hpp)
• Sparse な FPS 演算 (fps/sparse.hpp)
• modint/mod-sqrt.hpp

Verified with

• verify/fps/LC_convolution_mod.relaxed.test.cpp
• verify/fps/LC_convolution_mod.semirelaxed.test.cpp
• verify/fps/LC_exp_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_exp_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_inv_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_inv_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_log_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_log_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_pow_of_formal_power_series_sparse.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series.relaxed.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series.test.cpp
• verify/fps/LC_sqrt_of_formal_power_series_sparse.test.cpp

Code

#pragma once

unsigned int ModPow(unsigned int a, unsigned long long n, unsigned int m) {
  unsigned long long x = a, y = 1;
  while (n) {
    if (n & 1) y = y * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return y;
}

#line 2 "modint/mod-pow.hpp"

unsigned int ModPow(unsigned int a, unsigned long long n, unsigned int m) {
  unsigned long long x = a, y = 1;
  while (n) {
    if (n & 1) y = y * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return y;
}

Back to top page