subarray_gcd.hpp¶
For every right endpoint, group all nonempty suffixes by gcd in O(n log V) total groups.
\[
\displaystyle \gcd(a_l,\dots,a_r)
\]
Implementation¶
#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> &values) {
static_assert(std::is_integral_v<Int>);
std::vector<std::vector<std::pair<Int, std::uint64_t>>> result;
result.reserve(values.size());
std::vector<std::pair<Int, std::uint64_t>> previous;
for (Int value : values) {
std::vector<std::pair<Int, std::uint64_t>> current;
auto append = [&](Int divisor, std::uint64_t count) {
if (!current.empty() && current.back().first == divisor) {
current.back().second += count;
} else {
current.emplace_back(divisor, count);
}
};
append(std::abs(value), 1);
for (auto [divisor, count] : previous) {
append(std::gcd(divisor, value), count);
}
result.push_back(current);
previous = std::move(current);
}
return result;
}
/// @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> &values) {
std::map<Int, std::uint64_t> counts;
for (const auto &groups : subarray_gcd_suffix_groups(values)) {
for (auto [divisor, count] : groups) {
counts[divisor] += count;
}
}
return {counts.begin(), counts.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> &values) {
static_assert(std::is_integral_v<Int>);
std::vector<std::vector<std::pair<Int, std::uint64_t>>> result;
result.reserve(values.size());
std::vector<std::pair<Int, std::uint64_t>> previous;
for (Int value : values) {
std::vector<std::pair<Int, std::uint64_t>> current;
auto append = [&](Int divisor, std::uint64_t count) {
if (!current.empty() && current.back().first == divisor) {
current.back().second += count;
} else {
current.emplace_back(divisor, count);
}
};
append(std::abs(value), 1);
for (auto [divisor, count] : previous) {
append(std::gcd(divisor, value), count);
}
result.push_back(current);
previous = std::move(current);
}
return result;
}
/// @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> &values) {
std::map<Int, std::uint64_t> counts;
for (const auto &groups : subarray_gcd_suffix_groups(values)) {
for (auto [divisor, count] : groups) {
counts[divisor] += count;
}
}
return {counts.begin(), counts.end()};
}
} // namespace noya