竞赛编程优化求助：区间非gcd元素计数问题

针对你的问题，核心是将统计区间内与区间GCD不同的元素数量转化为区间长度减去区间内等于GCD的元素数量，结合预处理实现高效查询：

预处理步骤 #

1. 稀疏表预处理区间GCD
   你已经实现的这一步可以保留：利用GCD的结合律与幂等性构建稀疏表，实现O(1)时间查询任意区间[a,b]的GCD值G，预处理时间O(n log n)，空间O(n log n)。

2. 哈希表+有序列表预处理元素位置
   遍历数组，用哈希表记录每个数值对应的所有出现下标，每个数值的下标列表天然保持有序（按遍历顺序添加即可）。例如，哈希表pos_map中，pos_map[x]是一个数组，存储所有值为x的元素在原数组中的下标。预处理时间O(n)，空间O(n)。

查询步骤 #

对于每次查询[a,b]：

• 用稀疏表快速得到区间GCD值G。
• 查找pos_map中是否存在G：
  • 若不存在，说明区间内没有等于G的元素，结果为b - a + 1。
  • 若存在，在pos_map[G]这个有序数组中，用二分查找找到第一个≥a的下标位置left，以及最后一个≤b的下标位置right。若left > right，则等于G的元素数量为0；否则数量为right - left + 1。
• 最终结果 = 区间长度(b - a + 1) - 等于G的元素数量。

复杂度分析 #

• 预处理：O(n log n)（稀疏表） + O(n)（哈希表），总时间O(n log n)，空间O(n log n)。
• 单次查询：O(1)（查GCD） + O(log k)（二分查找，k为G在数组中的出现次数），远优于原遍历统计的O(n)时间，适合大规模查询场景（如q=1e5）。

关键细节说明 #

• 无需担心区间GCDG未在区间中出现的情况（例如区间[4,6,8]的GCD为2，但区间内无2）：此时二分查找会返回数量0，结果直接等于区间长度，符合预期。
• 下标注意：确保数组下标与查询的a,b一致（若题目中a,b是1-based，预处理时需对应调整）。

内容的提问来源于stack exchange，提问作者Leonardo Lovera