cplib/pow_mod_ull.hpp

• View this file on GitHub
• Last update: 2025-12-24 16:17:55+09:00
• Include: #include "cplib/pow_mod_ull.hpp"

Required by

• cplib/is_prime.hpp
• cplib/miller_rabin.hpp

Verified with

• test/aoj/ALDS1_1_C/ALDS1_1_C-test-00.cpp
• test/library-checker/primality_test/primality_test-test-00.cpp
• test/yukicoder/8030/8030-test-00.cpp

Code

#pragma once

#include <cstdint>

namespace cplib {

// (x ^ n) mod m を繰り返し二乗法で求める
// x >= 0, n >= 0, m >= 1
uint64_t pow_mod_ull(uint64_t x, uint64_t n, const uint64_t m) {
    uint64_t result = ((n % 2 == 1) ? x : 1) % m;
    for (n /= 2; n > 0; n /= 2) {
        x = static_cast<uint64_t>(__uint128_t(x) * __uint128_t(x) %
                                  __uint128_t(m));
        if (n % 2 == 1) {
            result = static_cast<uint64_t>(__uint128_t(result) *
                                           __uint128_t(x) % __uint128_t(m));
        }
    }
    return result;
}

}  // namespace cplib

#line 2 "cplib/pow_mod_ull.hpp"

#include <cstdint>

namespace cplib {

// (x ^ n) mod m を繰り返し二乗法で求める
// x >= 0, n >= 0, m >= 1
uint64_t pow_mod_ull(uint64_t x, uint64_t n, const uint64_t m) {
    uint64_t result = ((n % 2 == 1) ? x : 1) % m;
    for (n /= 2; n > 0; n /= 2) {
        x = static_cast<uint64_t>(__uint128_t(x) * __uint128_t(x) %
                                  __uint128_t(m));
        if (n % 2 == 1) {
            result = static_cast<uint64_t>(__uint128_t(result) *
                                           __uint128_t(x) % __uint128_t(m));
        }
    }
    return result;
}

}  // namespace cplib

Back to top page