math/barrett.hpp

• View this file on GitHub
• Last update: 2025-11-01 00:19:27+09:00
• Include: #include "math/barrett.hpp"

Required by

• modint/dynamic-modint.hpp

Verified with

• verify/fps/LC_montmort_number_mod.test.cpp
• verify/modint/LC_binomial_coefficient_prime_mod.test.cpp
• verify/modint/UNIT_dynamic_modint.test.cpp

Code

#pragma once

struct barrett {
  unsigned int _m;
  unsigned long long im;
  explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
  unsigned int umod() const { return _m; }
  unsigned int mul(unsigned int a, unsigned int b) const {
    unsigned long long z = a;
    z *= b;
#ifdef _MSC_VER
    unsigned long long x;
    _umul128(z, im, &x);
#else
    unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
    unsigned long long y = x * _m;
    return (unsigned int)(z - y + (z < y ? _m : 0));
  }
};

#line 2 "math/barrett.hpp"

struct barrett {
  unsigned int _m;
  unsigned long long im;
  explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
  unsigned int umod() const { return _m; }
  unsigned int mul(unsigned int a, unsigned int b) const {
    unsigned long long z = a;
    z *= b;
#ifdef _MSC_VER
    unsigned long long x;
    _umul128(z, im, &x);
#else
    unsigned long long x = (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
    unsigned long long y = x * _m;
    return (unsigned int)(z - y + (z < y ? _m : 0));
  }
};

Back to top page