pow_mod
(src/math/pow_mod.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/math/pow_mod.hpp"

pow_mod

ll pow_mod(ll x, ll n, ll mod)

$x^{n}$ を $\mathrm{mod}$ で割った余りを返します．

制約

• $0 \leq n$
• $1 \leq \mathrm{mod}$

計算量

• $O(\log n)$

Depends on

• template (src/template/template.hpp)

Required by

• convolution (src/convolution/convolution.hpp)
• convolution_arbitrary (src/convolution/convolution_arbitrary.hpp)
• convolution_ll (src/convolution/convolution_ll.hpp)
• FormalPowerSeries (src/fps/formal_power_series.hpp)
• FormalPowerSeriesArbitrary (src/fps/formal_power_series_arbitrary.hpp)
• FormalPowerSeriesLL (src/fps/formal_power_series_ll.hpp)
• primitive_root (src/math/primitive_root.hpp)
• wildcard_pattern_matching (src/string/wildcard_pattern_matching.hpp)

Verified with

• verify/aizu_online_judge/ntl/power.test.cpp
• verify/library_checker/convolution/convolution.test.cpp
• verify/library_checker/convolution/convolution_mod_1000000007.test.cpp
• verify/library_checker/other/find_linear_recurrence.test.cpp
• verify/library_checker/other/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/library_checker/polynomial/division_of_polynomial.test.cpp
• verify/library_checker/polynomial/exp_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/inv_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/log_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/polynomial_taylor_shift.test.cpp
• verify/library_checker/polynomial/pow_of_formal_power_series.test.cpp
• verify/library_checker/polynomial/product_of_polynomial_sequence.test.cpp
• verify/library_checker/string/wildcard_pattern_matching.test.cpp
• verify/library_checker/tree/frequency_table_of_tree_distance.test.cpp
• verify/unit_test/convolution/convolution_ll.test.cpp
• verify/yukicoder/1559.test.cpp

Code

#pragma once
#include "../template/template.hpp"
constexpr long long pow_mod(long long x, long long n, const long long mod) {
    assert(n >= 0 and mod >= 1);
    x %= mod;
    if(x < 0) x += mod;
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/pow_mod.hpp"
constexpr long long pow_mod(long long x, long long n, const long long mod) {
    assert(n >= 0 and mod >= 1);
    x %= mod;
    if(x < 0) x += mod;
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

Back to top page