modint/barrett-reduction.hpp

• View this file on GitHub
• Last update: 2022-02-08 14:09:38+09:00
• Include: #include "modint/barrett-reduction.hpp"

Required by

• modint (2^{30} 未満の任意 mod 用) (modint/arbitrary-modint.hpp)
• 任意mod二項係数 (modulo/arbitrary-mod-binomial.hpp)
• 多変数巡回畳み込み (ntt/multivariate-circular-convolution.hpp)

Verified with

• verify/verify-unit-test/arbitrary-modint.test.cpp
• verify/verify-unit-test/barrett-reduction.test.cpp
• verify/verify-unit-test/garner-bigint.test.cpp
• verify/verify-yosupo-math/yosupo-binomial-coefficient-large.test.cpp
• verify/verify-yosupo-math/yosupo-binomial-coefficient-prime-mod.test.cpp
• verify/verify-yosupo-math/yosupo-binomial-coefficient.test.cpp
• verify/verify-yosupo-math/yosupo-determinant-arbitrary-mod.test.cpp
• verify/verify-yosupo-ntt/yosupo-convolution-arbitraryntt-arbitrarymodint.test.cpp
• verify/verify-yosupo-ntt/yosupo-multivariate-circular-convolution.test.cpp

Code

#pragma once

#include <utility>
using namespace std;

struct Barrett {
  using u32 = unsigned int;
  using i64 = long long;
  using u64 = unsigned long long;
  u32 m;
  u64 im;
  Barrett() : m(), im() {}
  Barrett(int n) : m(n), im(u64(-1) / m + 1) {}
  constexpr inline i64 quo(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    return m <= r ? x - 1 : x;
  }
  constexpr inline i64 rem(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    return m <= r ? r + m : r;
  }
  constexpr inline pair<i64, int> quorem(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    if (m <= r) return {x - 1, r + m};
    return {x, r};
  }
  constexpr inline i64 pow(u64 n, i64 p) {
    u32 a = rem(n), r = m == 1 ? 0 : 1;
    while (p) {
      if (p & 1) r = rem(u64(r) * a);
      a = rem(u64(a) * a);
      p >>= 1;
    }
    return r;
  }
};

#line 2 "modint/barrett-reduction.hpp"

#include <utility>
using namespace std;

struct Barrett {
  using u32 = unsigned int;
  using i64 = long long;
  using u64 = unsigned long long;
  u32 m;
  u64 im;
  Barrett() : m(), im() {}
  Barrett(int n) : m(n), im(u64(-1) / m + 1) {}
  constexpr inline i64 quo(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    return m <= r ? x - 1 : x;
  }
  constexpr inline i64 rem(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    return m <= r ? r + m : r;
  }
  constexpr inline pair<i64, int> quorem(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    if (m <= r) return {x - 1, r + m};
    return {x, r};
  }
  constexpr inline i64 pow(u64 n, i64 p) {
    u32 a = rem(n), r = m == 1 ? 0 : 1;
    while (p) {
      if (p & 1) r = rem(u64(r) * a);
      a = rem(u64(a) * a);
      p >>= 1;
    }
    return r;
  }
};

Back to top page