src/math/modular-arithmetic/mod-pow.hpp

• View this file on GitHub
• Last update: 2023-07-06 04:55:57+09:00
• Include: #include "src/math/modular-arithmetic/mod-pow.hpp"

Depends on

• src/cpp-template/header/int-alias.hpp

Required by

• src/math/convolution/modint-convolution.hpp
• src/string/wildcard-pattern-matching.hpp

Verified with

• test/atcoder/abc307_h.test.cpp
• test/library-checker/modint_convolution.test.cpp

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"

namespace luz {

  i64 mod_pow(i64 b, i64 e, i64 mod) {
    if (mod == 1) return 0;
    i64 ans{1};

    while (e) {
      if (e & 1) {
        ans = ans * b % mod;
      }
      b = b * b % mod;
      e /= 2;
    }

    return ans;
  }

}

#line 2 "src/math/modular-arithmetic/mod-pow.hpp"

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;

}
#line 4 "src/math/modular-arithmetic/mod-pow.hpp"

namespace luz {

  i64 mod_pow(i64 b, i64 e, i64 mod) {
    if (mod == 1) return 0;
    i64 ans{1};

    while (e) {
      if (e & 1) {
        ans = ans * b % mod;
      }
      b = b * b % mod;
      e /= 2;
    }

    return ans;
  }

}

Back to top page