verify/aoj-NTL_1_B-mod_pow.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_B

Depends on

algorithm/Math/ModularArithmetic/mod_pow.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_B"

#include <iostream>

#include "../algorithm/Math/ModularArithmetic/mod_pow.hpp"

int main() {
    constexpr int MOD = 1e9 + 7;

    int m, n;
    std::cin >> m >> n;

    auto ans = algorithm::mod_pow(m, n, MOD);
    std::cout << ans << std::endl;
}

#line 1 "verify/aoj-NTL_1_B-mod_pow.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_B"

#include <iostream>

#line 1 "algorithm/Math/ModularArithmetic/mod_pow.hpp"



#include <cassert>

namespace algorithm {

// 繰り返し二乗法（mod付き）．O(logK).
constexpr long long mod_pow(long long n, long long k, int mod) {
    assert(k >= 0);
    assert(mod >= 1);
    long long res = 1;
    n %= mod;
    while(k > 0) {
        if(k & 1LL) res = res * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm


#line 6 "verify/aoj-NTL_1_B-mod_pow.test.cpp"

int main() {
    constexpr int MOD = 1e9 + 7;

    int m, n;
    std::cin >> m >> n;

    auto ans = algorithm::mod_pow(m, n, MOD);
    std::cout << ans << std::endl;
}