number_theory/barrett.hpp

• View this file on GitHub
• Last update: 2026-04-03 09:13:19+09:00
• Include: #include "number_theory/barrett.hpp"

Required by

• number_theory/dynamic_mod_int.hpp

Verified with

• number_theory/test/dynamic_modint_stress.test.cpp

Code

#pragma once

struct Barrett {
    unsigned m;
    unsigned long long im;
    explicit Barrett(unsigned m) : m(m), im(-1ull / m + 1) {}
    unsigned mul(unsigned x, unsigned y) const {
        unsigned long long z = (unsigned long long)x * y;
        unsigned long long q = ((__uint128_t)z * im) >> 64;
        unsigned long long t = q * m;
        return z - t + (z < t ? m : 0);
    }
};

#line 2 "number_theory/barrett.hpp"

struct Barrett {
    unsigned m;
    unsigned long long im;
    explicit Barrett(unsigned m) : m(m), im(-1ull / m + 1) {}
    unsigned mul(unsigned x, unsigned y) const {
        unsigned long long z = (unsigned long long)x * y;
        unsigned long long q = ((__uint128_t)z * im) >> 64;
        unsigned long long t = q * m;
        return z - t + (z < t ? m : 0);
    }
};

Back to top page