This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "mod/barrett.hpp"
#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); } };