min_of_mod_linear.hpp¶
求有限区间内 \((ax+b)\bmod m\) 的最小值及取得它的下标。
\[
\displaystyle \min_{0\le x<n}(ax+b)\bmod m
\]
Complexity: Time: \(O(\log (m + 1))\). Space: \(O(1)\), where \(m\) is the modulus.
Source: maspy
AC 记录：min_of_mod_of_linear。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log(m+1)). Space: O(1), where m is the modulus.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <utility>
namespace noya {
/// @brief Return an index attaining the minimum of
/// `(mul * x + add) mod mod` for `0 <= x < cnt`, together with that minimum.
/// Requires 1 <= cnt,mod <= 10^9 and 0 <= mul,add < mod.
/// Continued-fraction neighbors describe arithmetic runs of record minima.
inline std::pair<std::uint64_t, std::uint64_t>
min_of_mod_linear_argument(std::uint64_t cnt, std::uint64_t mod,
std::uint64_t mul, std::uint64_t add) {
assert(cnt >= 1 && mod >= 1);
assert(mul < mod && add < mod);
assert(cnt <= 1'000'000'000ULL && mod <= 1'000'000'000ULL);
std::uint64_t g = std::gcd(mul, mod);
std::int64_t a = mul / g, m = mod / g;
// ld/rd are neighbor denominators; dl/dr are their determinants against a/m.
std::int64_t ld = 1;
std::int64_t rd = 1;
std::int64_t dl = m - a;
std::int64_t dr = a;
std::int64_t idx = 0;
std::int64_t val = add / g;
while (val != 0) {
std::int64_t quo = dr / dl;
dr %= dl;
if (dr == 0) {
--quo;
dr = dl;
}
rd += quo * ld;
while (true) {
quo = std::max<std::int64_t>(0, (dl - val + dr - 1) / dr);
if (dl - quo * dr <= 0) {
break;
}
dl -= quo * dr;
ld += quo * rd;
quo = val / dl;
if (std::uint64_t(idx + ld * quo) >= cnt) {
// Keep the last record minimum inside the query prefix.
idx += std::int64_t((cnt - 1 - std::uint64_t(idx)) /
std::uint64_t(ld)) * ld;
return {std::uint64_t(idx), (mul * std::uint64_t(idx) + add) % mod};
}
idx += ld * quo;
val -= quo * dl;
if (val == 0) return {std::uint64_t(idx), add % g};
}
quo = dl / dr;
dl -= quo * dr;
ld += quo * rd;
}
return {std::uint64_t(idx), (mul * std::uint64_t(idx) + add) % mod};
}
/// @brief Return the minimum residue of a linear function on
/// `0 <= x < cnt` using the continued-fraction prefix-minimum decomposition.
inline std::uint64_t min_of_mod_linear(std::uint64_t cnt, std::uint64_t mod,
std::uint64_t mul, std::uint64_t add) {
return min_of_mod_linear_argument(cnt, mod, mul, add).second;
}
} // namespace noya
// NOYA_MIN_OF_MOD_LINEAR_HPP
#ifndef NOYA_MIN_OF_MOD_LINEAR_HPP
#define NOYA_MIN_OF_MOD_LINEAR_HPP 1
/// @complexity Time: O(log(m+1)). Space: O(1), where m is the modulus.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <utility>
namespace noya {
/// @brief Return an index attaining the minimum of
/// `(mul * x + add) mod mod` for `0 <= x < cnt`, together with that minimum.
/// Requires 1 <= cnt,mod <= 10^9 and 0 <= mul,add < mod.
/// Continued-fraction neighbors describe arithmetic runs of record minima.
inline std::pair<std::uint64_t, std::uint64_t>
min_of_mod_linear_argument(std::uint64_t cnt, std::uint64_t mod,
std::uint64_t mul, std::uint64_t add) {
assert(cnt >= 1 && mod >= 1);
assert(mul < mod && add < mod);
assert(cnt <= 1'000'000'000ULL && mod <= 1'000'000'000ULL);
std::uint64_t g = std::gcd(mul, mod);
std::int64_t a = mul / g, m = mod / g;
// ld/rd are neighbor denominators; dl/dr are their determinants against a/m.
std::int64_t ld = 1;
std::int64_t rd = 1;
std::int64_t dl = m - a;
std::int64_t dr = a;
std::int64_t idx = 0;
std::int64_t val = add / g;
while (val != 0) {
std::int64_t quo = dr / dl;
dr %= dl;
if (dr == 0) {
--quo;
dr = dl;
}
rd += quo * ld;
while (true) {
quo = std::max<std::int64_t>(0, (dl - val + dr - 1) / dr);
if (dl - quo * dr <= 0) {
break;
}
dl -= quo * dr;
ld += quo * rd;
quo = val / dl;
if (std::uint64_t(idx + ld * quo) >= cnt) {
// Keep the last record minimum inside the query prefix.
idx += std::int64_t((cnt - 1 - std::uint64_t(idx)) /
std::uint64_t(ld)) * ld;
return {std::uint64_t(idx), (mul * std::uint64_t(idx) + add) % mod};
}
idx += ld * quo;
val -= quo * dl;
if (val == 0) return {std::uint64_t(idx), add % g};
}
quo = dl / dr;
dl -= quo * dr;
ld += quo * rd;
}
return {std::uint64_t(idx), (mul * std::uint64_t(idx) + add) % mod};
}
/// @brief Return the minimum residue of a linear function on
/// `0 <= x < cnt` using the continued-fraction prefix-minimum decomposition.
inline std::uint64_t min_of_mod_linear(std::uint64_t cnt, std::uint64_t mod,
std::uint64_t mul, std::uint64_t add) {
return min_of_mod_linear_argument(cnt, mod, mul, add).second;
}
} // namespace noya
#endif // NOYA_MIN_OF_MOD_LINEAR_HPP
/// @complexity Time: O(log(m+1)). Space: O(1), where m is the modulus.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <utility>
namespace noya {
/// @brief Return an index attaining the minimum of
/// `(mul * x + add) mod mod` for `0 <= x < cnt`, together with that minimum.
/// Requires 1 <= cnt,mod <= 10^9 and 0 <= mul,add < mod.
/// Continued-fraction neighbors describe arithmetic runs of record minima.
inline std::pair<std::uint64_t, std::uint64_t>
min_of_mod_linear_argument(std::uint64_t cnt, std::uint64_t mod,
std::uint64_t mul, std::uint64_t add) {
assert(cnt >= 1 && mod >= 1);
assert(mul < mod && add < mod);
assert(cnt <= 1'000'000'000ULL && mod <= 1'000'000'000ULL);
std::uint64_t g = std::gcd(mul, mod);
std::int64_t a = mul / g, m = mod / g;
// ld/rd are neighbor denominators; dl/dr are their determinants against a/m.
std::int64_t ld = 1;
std::int64_t rd = 1;
std::int64_t dl = m - a;
std::int64_t dr = a;
std::int64_t idx = 0;
std::int64_t val = add / g;
while (val != 0) {
std::int64_t quo = dr / dl;
dr %= dl;
if (dr == 0) {
--quo;
dr = dl;
}
rd += quo * ld;
while (true) {
quo = std::max<std::int64_t>(0, (dl - val + dr - 1) / dr);
if (dl - quo * dr <= 0) {
break;
}
dl -= quo * dr;
ld += quo * rd;
quo = val / dl;
if (std::uint64_t(idx + ld * quo) >= cnt) {
// Keep the last record minimum inside the query prefix.
idx += std::int64_t((cnt - 1 - std::uint64_t(idx)) /
std::uint64_t(ld)) * ld;
return {std::uint64_t(idx), (mul * std::uint64_t(idx) + add) % mod};
}
idx += ld * quo;
val -= quo * dl;
if (val == 0) return {std::uint64_t(idx), add % g};
}
quo = dl / dr;
dl -= quo * dr;
ld += quo * rd;
}
return {std::uint64_t(idx), (mul * std::uint64_t(idx) + add) % mod};
}
/// @brief Return the minimum residue of a linear function on
/// `0 <= x < cnt` using the continued-fraction prefix-minimum decomposition.
inline std::uint64_t min_of_mod_linear(std::uint64_t cnt, std::uint64_t mod,
std::uint64_t mul, std::uint64_t add) {
return min_of_mod_linear_argument(cnt, mod, mul, add).second;
}
} // namespace noya
// NOYA_MIN_OF_MOD_LINEAR_HPP