mod/barrett.hpp

• View this file on GitHub
• Last update: 2023-10-17 07:10:25+09:00
• Include: #include "mod/barrett.hpp"
• Link: https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp

Required by

• graph/count/count_labeled_bipartite.hpp
• linalg/det.hpp
• mod/binomial.hpp
• mod/dynamic_modint.hpp
• mod/dynamic_modint_64.hpp
• mod/mod_kth_root.hpp
• mod/mod_log.hpp
• mod/mod_pow.hpp
• mod/mod_sqrt.hpp
• mod/multiplicative_convolution_mod_p.hpp
• mod/primitive_root.hpp
• mod/tetration.hpp
• nt/crt.hpp
• nt/four_square.hpp
• nt/gaussian_integers.hpp
• nt/three_square.hpp
• nt/three_triangular.hpp
• poly/fps_sqrt.hpp
• poly/multivar_convolution_cyclic.hpp

Verified with

• test/library_checker/convolution/convolution_mod_107_dmint.test.cpp
• test/library_checker/convolution/convolution_mod_dmint.test.cpp
• test/library_checker/convolution/convolution_mod_setntt.test.cpp
• test/library_checker/convolution/mul_modp_conv.test.cpp
• test/library_checker/math/binomial_coefficient.test.cpp
• test/library_checker/math/discrete_logarithm_mod.test.cpp
• test/library_checker/math/gaussian_integers.test.cpp
• test/library_checker/math/kth_root_mod.test.cpp
• test/library_checker/math/multivariate_convolution_cyclic.test.cpp
• test/library_checker/math/primitive_root.test.cpp
• test/library_checker/math/sqrt_mod.test.cpp
• test/library_checker/math/tetration.test.cpp
• test/library_checker/matrix/det_mod.test.cpp
• test/library_checker/matrix/matrix_det.test.cpp
• test/library_checker/polynomial/exp_of_fps_dmint.test.cpp
• test/library_checker/polynomial/exp_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/inv_of_fps.test.cpp
• test/library_checker/polynomial/inv_of_fps_dmint.test.cpp
• test/library_checker/polynomial/inv_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/log_of_fps_dmint.test.cpp
• test/library_checker/polynomial/log_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/pow_of_fps_dmint.test.cpp
• test/library_checker/polynomial/pow_of_fps_sparse_dmint.test.cpp
• test/library_checker/polynomial/sqrt_of_fps.test.cpp
• test/library_checker/polynomial/sqrt_of_fps_sparse.test.cpp
• test/mytest/31bit_modint.test.cpp
• test/mytest/O1_inv.test.cpp
• test/mytest/count_bipartite.test.cpp
• test/mytest/four_square.test.cpp
• test/mytest/geometric_sequence_sum.test.cpp
• test/mytest/three_square.test.cpp
• test/mytest/three_triangular.test.cpp
• test/yukicoder/1025.test.cpp
• test/yukicoder/1303.test.cpp
• test/yukicoder/1339.test.cpp
• test/yukicoder/1593.test.cpp
• test/yukicoder/1667.test.cpp
• test/yukicoder/1783.test.cpp
• test/yukicoder/187.test.cpp
• test/yukicoder/1956.test.cpp
• test/yukicoder/2119.test.cpp
• test/yukicoder/2120.test.cpp
• test/yukicoder/2181.test.cpp
• test/yukicoder/2613.test.cpp
• test/yukicoder/590.test.cpp
• test_atcoder/abc222g.test.cpp
• test_atcoder/abc270_g.test.cpp
• test_atcoder/abc281g.test.cpp
• test_atcoder/abc335g.test.cpp
• test_atcoder/agc058d2.test.cpp

Code

#pragma once

// https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
struct Barrett {
  u32 m;
  u64 im;
  explicit Barrett(u32 m = 1) : m(m), im(u64(-1) / m + 1) {}
  u32 umod() const { return m; }
  u32 modulo(u64 z) {
    if (m == 1) return 0;
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    return (z - y + (z < y ? m : 0));
  }
  u64 floor(u64 z) {
    if (m == 1) return z;
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    return (z < y ? x - 1 : x);
  }
  pair<u64, u32> divmod(u64 z) {
    if (m == 1) return {z, 0};
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    if (z < y) return {x - 1, z - y + m};
    return {x, z - y};
  }
  u32 mul(u32 a, u32 b) { return modulo(u64(a) * b); }
};

struct Barrett_64 {
  u128 mod, mh, ml;

  explicit Barrett_64(u64 mod = 1) : mod(mod) {
    u128 m = u128(-1) / mod;
    if (m * mod + mod == u128(0)) ++m;
    mh = m >> 64;
    ml = m & u64(-1);
  }

  u64 umod() const { return mod; }

  u64 modulo(u128 x) {
    u128 z = (x & u64(-1)) * ml;
    z = (x & u64(-1)) * mh + (x >> 64) * ml + (z >> 64);
    z = (x >> 64) * mh + (z >> 64);
    x -= z * mod;
    return x < mod ? x : x - mod;
  }

  u64 mul(u64 a, u64 b) { return modulo(u128(a) * b); }
};

#line 2 "mod/barrett.hpp"

// https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
struct Barrett {
  u32 m;
  u64 im;
  explicit Barrett(u32 m = 1) : m(m), im(u64(-1) / m + 1) {}
  u32 umod() const { return m; }
  u32 modulo(u64 z) {
    if (m == 1) return 0;
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    return (z - y + (z < y ? m : 0));
  }
  u64 floor(u64 z) {
    if (m == 1) return z;
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    return (z < y ? x - 1 : x);
  }
  pair<u64, u32> divmod(u64 z) {
    if (m == 1) return {z, 0};
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    if (z < y) return {x - 1, z - y + m};
    return {x, z - y};
  }
  u32 mul(u32 a, u32 b) { return modulo(u64(a) * b); }
};

struct Barrett_64 {
  u128 mod, mh, ml;

  explicit Barrett_64(u64 mod = 1) : mod(mod) {
    u128 m = u128(-1) / mod;
    if (m * mod + mod == u128(0)) ++m;
    mh = m >> 64;
    ml = m & u64(-1);
  }

  u64 umod() const { return mod; }

  u64 modulo(u128 x) {
    u128 z = (x & u64(-1)) * ml;
    z = (x & u64(-1)) * mh + (x >> 64) * ml + (z >> 64);
    z = (x >> 64) * mh + (z >> 64);
    x -= z * mod;
    return x < mod ? x : x - mod;
  }

  u64 mul(u64 a, u64 b) { return modulo(u128(a) * b); }
};

Back to top page