subarray_gcd.hpp¶
按每个右端点压缩所有子数组 gcd；用于统计 gcd 等于某值的子数组数量或贡献。
\[
\displaystyle \gcd(a_l,\dots,a_r)
\]
Complexity: Time: O(n log A). Space: O(log A) frontier per endpoint, excluding aggregate output.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log A).
/// Space: O(log A) frontier per endpoint, excluding aggregate output.
#include <algorithm>
#include <cstdlib>
#include <cstdint>
#include <map>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief For every right endpoint, group all nonempty suffixes by gcd in
/// O(n log V) total groups.
template <class Int>
std::vector<std::vector<std::pair<Int, std::uint64_t>>>
subarray_gcd_suffix_groups(const std::vector<Int> &vs) {
static_assert(std::is_integral_v<Int>);
std::vector<std::vector<std::pair<Int, std::uint64_t>>> res;
res.reserve(vs.size());
std::vector<std::pair<Int, std::uint64_t>> pre;
for (Int val : vs) {
std::vector<std::pair<Int, std::uint64_t>> cur;
auto app = [&](Int div, std::uint64_t cnt) {
if (!cur.empty() && cur.back().first == div) {
cur.back().second += cnt;
} else {
cur.emplace_back(div, cnt);
}
};
app(std::abs(val), 1);
for (auto [div, cnt] : pre) {
app(std::gcd(div, val), cnt);
}
res.push_back(cur);
pre = std::move(cur);
}
return res;
}
/// @brief Count subarrays by their gcd; returned pairs are sorted by gcd.
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;
for (const auto &gro : subarray_gcd_suffix_groups(vs)) {
for (auto [div, cnt] : gro) {
cou[div] += cnt;
}
}
return {cou.begin(), cou.end()};
}
} // namespace noya
#ifndef NOYA_SUBARRAY_GCD_HPP
#define NOYA_SUBARRAY_GCD_HPP 1
/// @complexity Time: O(n log A).
/// Space: O(log A) frontier per endpoint, excluding aggregate output.
#include <algorithm>
#include <cstdlib>
#include <cstdint>
#include <map>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief For every right endpoint, group all nonempty suffixes by gcd in
/// O(n log V) total groups.
template <class Int>
std::vector<std::vector<std::pair<Int, std::uint64_t>>>
subarray_gcd_suffix_groups(const std::vector<Int> &vs) {
static_assert(std::is_integral_v<Int>);
std::vector<std::vector<std::pair<Int, std::uint64_t>>> res;
res.reserve(vs.size());
std::vector<std::pair<Int, std::uint64_t>> pre;
for (Int val : vs) {
std::vector<std::pair<Int, std::uint64_t>> cur;
auto app = [&](Int div, std::uint64_t cnt) {
if (!cur.empty() && cur.back().first == div) {
cur.back().second += cnt;
} else {
cur.emplace_back(div, cnt);
}
};
app(std::abs(val), 1);
for (auto [div, cnt] : pre) {
app(std::gcd(div, val), cnt);
}
res.push_back(cur);
pre = std::move(cur);
}
return res;
}
/// @brief Count subarrays by their gcd; returned pairs are sorted by gcd.
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;
for (const auto &gro : subarray_gcd_suffix_groups(vs)) {
for (auto [div, cnt] : gro) {
cou[div] += cnt;
}
}
return {cou.begin(), cou.end()};
}
} // namespace noya
#endif // NOYA_SUBARRAY_GCD_HPP
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <map>
#include <numeric>
#include <type_traits>
#include <utility>
#include <vector>
/// @complexity Time: O(n log A).
/// Space: O(log A) frontier per endpoint, excluding aggregate output.
namespace noya {
/// @brief For every right endpoint, group all nonempty suffixes by gcd in
/// O(n log V) total groups.
template <class Int>
std::vector<std::vector<std::pair<Int, std::uint64_t>>>
subarray_gcd_suffix_groups(const std::vector<Int> &vs) {
static_assert(std::is_integral_v<Int>);
std::vector<std::vector<std::pair<Int, std::uint64_t>>> res;
res.reserve(vs.size());
std::vector<std::pair<Int, std::uint64_t>> pre;
for (Int val : vs) {
std::vector<std::pair<Int, std::uint64_t>> cur;
auto app = [&](Int div, std::uint64_t cnt) {
if (!cur.empty() && cur.back().first == div) {
cur.back().second += cnt;
} else {
cur.emplace_back(div, cnt);
}
};
app(std::abs(val), 1);
for (auto [div, cnt] : pre) {
app(std::gcd(div, val), cnt);
}
res.push_back(cur);
pre = std::move(cur);
}
return res;
}
/// @brief Count subarrays by their gcd; returned pairs are sorted by gcd.
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;
for (const auto &gro : subarray_gcd_suffix_groups(vs)) {
for (auto [div, cnt] : gro) {
cou[div] += cnt;
}
}
return {cou.begin(), cou.end()};
}
} // namespace noya