math/power.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/power.hpp"

Depends on

• math/base.hpp
• math/extgcd.hpp

Code

#pragma once

#include "./base.hpp"
#include "./extgcd.hpp"

#include <cassert>
#include <numeric>

namespace matumoto {
  // verify:AOJ_NTL_1_B
  constexpr ll power(ll a, ll e, ll p = -1) {
    assert(p != 0);
    assert(p >= -1);

    if (e < 0) {
      assert(p != -1 and gcd(a, p) == 1);
      ll x, y;
      extgcd(a, p, x, y);
      a = (x % p + p) % p;
      e *= -1;
    }

    ll res = 1;
    while (e > 0) {
      if (e & 1) {
        res *= a;
        if (p != -1)
          res %= p;
      }
      a *= a;
      if (p != -1)
        a %= p;
      e >>= 1;
    }
    return res;
  }
} // namespace matumoto

#line 2 "math/power.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 2 "math/extgcd.hpp"

#line 4 "math/extgcd.hpp"

namespace matumoto {
  constexpr ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y = y - (a / b) * x;
    return d;
  }
} // namespace matumoto
#line 5 "math/power.hpp"

#include <cassert>
#include <numeric>

namespace matumoto {
  // verify:AOJ_NTL_1_B
  constexpr ll power(ll a, ll e, ll p = -1) {
    assert(p != 0);
    assert(p >= -1);

    if (e < 0) {
      assert(p != -1 and gcd(a, p) == 1);
      ll x, y;
      extgcd(a, p, x, y);
      a = (x % p + p) % p;
      e *= -1;
    }

    ll res = 1;
    while (e > 0) {
      if (e & 1) {
        res *= a;
        if (p != -1)
          res %= p;
      }
      a *= a;
      if (p != -1)
        a %= p;
      e >>= 1;
    }
    return res;
  }
} // namespace matumoto

Back to top page