math/pow_mod.hpp

• View this file on GitHub
• Last update: 2023-02-06 17:52:27+09:00
• Include: #include "math/pow_mod.hpp"

Required by

• math/baby_step_giant_step.hpp

Verified with

• verify/aoj_ntl/aoj_ntl_1_b.test.cpp

Code

#pragma once

long long pow_mod(long long a, long long n, const long long mod) {
    assert(n >= 0 and mod >= 1);
    if (mod == 1) return 0;
    a %= mod;
    if (a < 0) a += mod;
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

#line 2 "math/pow_mod.hpp"

long long pow_mod(long long a, long long n, const long long mod) {
    assert(n >= 0 and mod >= 1);
    if (mod == 1) return 0;
    a %= mod;
    if (a < 0) a += mod;
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

Back to top page