subarray_gcd.hpp¶
按右端点压缩子数组 gcd；计数接口只保留当前压缩状态。支持有符号和无符号整数，输入绝对值须能由原类型表示。
\[
\displaystyle \gcd(a_l,\dots,a_r)
\]
Complexity: Time: \(O(n B)\) gcd calls, plus \(O(n B \log (D + 1))\) map work for counts. \(B\) is the value bit width and \(D\) the number of distinct gcds. Space: \(O(B)\) working frontier, plus \(O(n B)\) suffix output or \(O(D)\) counts.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n B) gcd calls, plus O(n B log(D+1)) map work for counts.
/// B is the value bit width and D the number of distinct gcds.
/// Space: O(B) working frontier, plus O(n B) suffix output or O(D) counts.
#include <cassert>
#include <cstdint>
#include <limits>
#include <map>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
namespace subarray_gcd_detail {
template <class Int>
void append(std::vector<std::pair<Int, std::uint64_t>> &cur, Int val) {
static_assert(std::is_integral_v<Int> && !std::is_same_v<Int, bool>);
if constexpr (std::is_signed_v<Int>) {
assert(val != std::numeric_limits<Int>::min());
if (val < 0) val = -val;
}
Int div = val;
std::uint64_t cnt = 1;
std::size_t k = 0;
for (auto [g, c] : cur) {
g = std::gcd(g, val);
if (g == div) {
cnt += c;
} else {
// k never passes the group being read, so compaction is safe in place.
cur[k++] = {div, cnt};
div = g;
cnt = c;
}
}
cur.resize(k);
cur.emplace_back(div, cnt);
}
} // namespace subarray_gcd_detail
/// @brief For every right endpoint, group all nonempty suffixes by gcd in
/// shortest-to-longest order. Magnitudes must be representable by Int.
template <class Int>
std::vector<std::vector<std::pair<Int, std::uint64_t>>>
subarray_gcd_suffix_groups(const std::vector<Int> &vs) {
std::vector<std::vector<std::pair<Int, std::uint64_t>>> res;
res.reserve(vs.size());
std::vector<std::pair<Int, std::uint64_t>> cur;
for (Int val : vs) {
subarray_gcd_detail::append(cur, val);
res.push_back(cur);
}
return res;
}
/// @brief Count subarrays by their gcd; returned pairs are sorted by gcd.
/// Magnitudes must be representable by Int; counts must fit uint64_t.
template <class Int>
std::vector<std::pair<Int, std::uint64_t>>
subarray_gcd_counts(const std::vector<Int> &vs) {
std::map<Int, std::uint64_t> cou;
std::vector<std::pair<Int, std::uint64_t>> cur;
for (Int val : vs) {
subarray_gcd_detail::append(cur, val);
for (auto [div, cnt] : cur) {
cou[div] += cnt;
}
}
return {cou.begin(), cou.end()};
}
} // namespace noya
// NOYA_SUBARRAY_GCD_HPP
#ifndef NOYA_SUBARRAY_GCD_HPP
#define NOYA_SUBARRAY_GCD_HPP 1
/// @complexity Time: O(n B) gcd calls, plus O(n B log(D+1)) map work for counts.
/// B is the value bit width and D the number of distinct gcds.
/// Space: O(B) working frontier, plus O(n B) suffix output or O(D) counts.
#include <cassert>
#include <cstdint>
#include <limits>
#include <map>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
namespace subarray_gcd_detail {
template <class Int>
void append(std::vector<std::pair<Int, std::uint64_t>> &cur, Int val) {
static_assert(std::is_integral_v<Int> && !std::is_same_v<Int, bool>);
if constexpr (std::is_signed_v<Int>) {
assert(val != std::numeric_limits<Int>::min());
if (val < 0) val = -val;
}
Int div = val;
std::uint64_t cnt = 1;
std::size_t k = 0;
for (auto [g, c] : cur) {
g = std::gcd(g, val);
if (g == div) {
cnt += c;
} else {
// k never passes the group being read, so compaction is safe in place.
cur[k++] = {div, cnt};
div = g;
cnt = c;
}
}
cur.resize(k);
cur.emplace_back(div, cnt);
}
} // namespace subarray_gcd_detail
/// @brief For every right endpoint, group all nonempty suffixes by gcd in
/// shortest-to-longest order. Magnitudes must be representable by Int.
template <class Int>
std::vector<std::vector<std::pair<Int, std::uint64_t>>>
subarray_gcd_suffix_groups(const std::vector<Int> &vs) {
std::vector<std::vector<std::pair<Int, std::uint64_t>>> res;
res.reserve(vs.size());
std::vector<std::pair<Int, std::uint64_t>> cur;
for (Int val : vs) {
subarray_gcd_detail::append(cur, val);
res.push_back(cur);
}
return res;
}
/// @brief Count subarrays by their gcd; returned pairs are sorted by gcd.
/// Magnitudes must be representable by Int; counts must fit uint64_t.
template <class Int>
std::vector<std::pair<Int, std::uint64_t>>
subarray_gcd_counts(const std::vector<Int> &vs) {
std::map<Int, std::uint64_t> cou;
std::vector<std::pair<Int, std::uint64_t>> cur;
for (Int val : vs) {
subarray_gcd_detail::append(cur, val);
for (auto [div, cnt] : cur) {
cou[div] += cnt;
}
}
return {cou.begin(), cou.end()};
}
} // namespace noya
#endif // NOYA_SUBARRAY_GCD_HPP
/// @complexity Time: O(n B) gcd calls, plus O(n B log(D+1)) map work for counts.
/// B is the value bit width and D the number of distinct gcds.
/// Space: O(B) working frontier, plus O(n B) suffix output or O(D) counts.
#include <cassert>
#include <cstdint>
#include <limits>
#include <map>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
namespace subarray_gcd_detail {
template <class Int>
void append(std::vector<std::pair<Int, std::uint64_t>> &cur, Int val) {
static_assert(std::is_integral_v<Int> && !std::is_same_v<Int, bool>);
if constexpr (std::is_signed_v<Int>) {
assert(val != std::numeric_limits<Int>::min());
if (val < 0) val = -val;
}
Int div = val;
std::uint64_t cnt = 1;
std::size_t k = 0;
for (auto [g, c] : cur) {
g = std::gcd(g, val);
if (g == div) {
cnt += c;
} else {
// k never passes the group being read, so compaction is safe in place.
cur[k++] = {div, cnt};
div = g;
cnt = c;
}
}
cur.resize(k);
cur.emplace_back(div, cnt);
}
} // namespace subarray_gcd_detail
/// @brief For every right endpoint, group all nonempty suffixes by gcd in
/// shortest-to-longest order. Magnitudes must be representable by Int.
template <class Int>
std::vector<std::vector<std::pair<Int, std::uint64_t>>>
subarray_gcd_suffix_groups(const std::vector<Int> &vs) {
std::vector<std::vector<std::pair<Int, std::uint64_t>>> res;
res.reserve(vs.size());
std::vector<std::pair<Int, std::uint64_t>> cur;
for (Int val : vs) {
subarray_gcd_detail::append(cur, val);
res.push_back(cur);
}
return res;
}
/// @brief Count subarrays by their gcd; returned pairs are sorted by gcd.
/// Magnitudes must be representable by Int; counts must fit uint64_t.
template <class Int>
std::vector<std::pair<Int, std::uint64_t>>
subarray_gcd_counts(const std::vector<Int> &vs) {
std::map<Int, std::uint64_t> cou;
std::vector<std::pair<Int, std::uint64_t>> cur;
for (Int val : vs) {
subarray_gcd_detail::append(cur, val);
for (auto [div, cnt] : cur) {
cou[div] += cnt;
}
}
return {cou.begin(), cou.end()};
}
} // namespace noya
// NOYA_SUBARRAY_GCD_HPP