题目描述

给定一个长度为 $n$ 的整数数组 $a$ (元素值 $a_i \ge 2$)。
给定一个函数 $f(k, a, l, r)$ 的伪代码：

function f(k, a, l, r): // 使用 1-based 索引
   ans := 0
   for i from l to r (inclusive):
      while k is divisible by a[i]:
         k := k / a[i]
      ans := ans + k // 将 *当前* k 的值加入 ans
   return ans

其中 l 和 r 是数组 a 的有效索引范围 ($1 \le l \le r \le n$)。

需要处理 $q$ 个查询，每个查询给定三个整数 $k, l, r$。对于每个查询，计算并输出 $f(k, a, l, r)$ 的值。

样例

输入 #1

2
5 3
2 3 5 7 11
2 1 5
2 2 4
2310 1 5
4 3
18 12 8 9
216 1 2
48 2 4
82944 1 4

输出 #1

5
6
1629
13
12
520

样例 1 解释 (第一个测试用例):
a = [2, 3, 5, 7, 11]

Query 1: k=2, l=1, r=5
i=1: a[1]=2. k=2. k is divisible by 2. k = 2/2 = 1. ans = 0 + 1 = 1.
i=2: a[2]=3. k=1. k not divisible by 3. ans = 1 + 1 = 2.
i=3: a[3]=5. k=1. k not divisible by 5. ans = 2 + 1 = 3.
i=4: a[4]=7. k=1. k not divisible by 7. ans = 3 + 1 = 4.
i=5: a[5]=11. k=1. k not divisible by 11. ans = 4 + 1 = 5.
Return 5.

Query 2: k=2, l=2, r=4
i=2: a[2]=3. k=2. k not divisible by 3. ans = 0 + 2 = 2.
i=3: a[3]=5. k=2. k not divisible by 5. ans = 2 + 2 = 4.
i=4: a[4]=7. k=2. k not divisible by 7. ans = 4 + 2 = 6.
Return 6.

Query 3: k=2310, l=1, r=5
2310 = 2 * 3 * 5 * 7 * 11
i=1: a[1]=2. k=2310. k /= 2 = 1155. ans = 0 + 1155 = 1155.
i=2: a[2]=3. k=1155. k /= 3 = 385. ans = 1155 + 385 = 1540.
i=3: a[3]=5. k=385. k /= 5 = 77. ans = 1540 + 77 = 1617.
i=4: a[4]=7. k=77. k /= 7 = 11. ans = 1617 + 11 = 1628.
i=5: a[5]=11. k=11. k /= 11 = 1. ans = 1628 + 1 = 1629.
* Return 1629.

算法 (离线查询 + 扫描线 + 数据结构/预处理)

$O(V \log V + n + q \cdot \log k \cdot d_{\max})$ (大致估计, $V=\max(k, a_i)$, $d_{max}$是最大因子数)

思路分析

1. 理解函数 f 的行为:
   函数 f 遍历指定范围 [l, r]。在每一步 i，它会修改变量 k，方法是尽可能多地除去因子 a[i]。然后，将修改后的 k 值累加到 ans 中。关键在于 k 的值是动态变化的，并且在循环的不同迭代中添加到 ans 的值可能不同。

2. 直接模拟的问题:
   如果对每个查询都直接模拟伪代码，复杂度大约是 $O(q \cdot n \cdot \log k)$（每次 while 循环最多进行 $O(\log k)$ 次除法），这在给定约束下会超时。

3. 离线处理与扫描线:
   查询是关于区间的，这提示我们可以使用离线处理或者扫描线技术。我们将所有查询存储起来，然后按照某种顺序处理数组 a，同时回答相关的查询。
   一个常见的策略是按查询的左端点 l 或右端点 r 对查询进行分组/排序。我们选择按左端点 l 处理。

4. 扫描线方法:
   我们想象一条扫描线从数组的左端（索引 0）移动到右端（索引 n-1）。当扫描线位于索引 l 时，我们处理所有左端点为 l 的查询 (k, l, r)。
   对于一个查询 (k, l, r)，我们需要计算 $\sum_{i=l}^{r} k_i$，其中 $k_i$ 是在第 i 步循环结束时 k 的值。
   设当前查询 q 的原始 k 值为 $k_q$。当我们在索引 l 处理这个查询时：

   • 首先，根据伪代码，我们需要模拟第 l 步：计算 $k_q^{(l)}$，即 $k_q$ 在除去所有因子 $a[l]$ 后的值。
   • 然后，我们需要计算后续步骤 $l+1, \dots, r$ 的贡献。
   • 观察到，从步骤 $l$ 到下一个步骤 $t$（$t > l$）之前，如果对于所有的 $j$ 满足 $l \le j < t$，$a[j]$ 都不能整除当前的 $k$ 值（即 $k_q^{(l)}$），那么在 $j=l, l+1, \dots, t-1$ 这些步骤中，添加到 ans 的值将保持不变，都等于 $k_q^{(l)}$。
   • 因此，我们需要找到第一个索引 $t$（$t > l$）使得 $a[t]$ 是当前 $k$ 值（即 $k_q^{(l)}$）的因子。
   • 令这个最小的 $t$ 为 next_change_point。
   • 情况 1: 如果 next_change_point >= r (注意查询是 1-based，代码是 0-based，这里假设我们使用代码的 0-based 索引，查询范围为 $[l, r)$)。这意味着在整个查询区间 $[l, r)$ 内，k 的值在步骤 l 之后将不再改变。因此，对于 $i = l, l+1, \dots, r-1$，累加到 ans 的值都是 $k_q^{(l)}$。总贡献为 $(r - l) \times k_q^{(l)}$。
   • 情况 2: 如果 next_change_point < r。这意味着在区间 $[l, \text{next\_change\_point})$ 内，累加到 ans 的值都是 $k_q^{(l)}$。这部分的贡献是 $(\text{next\_change\_point} - l) \times k_q^{(l)}$。对于从 next_change_point 开始的剩余部分，我们需要在扫描线到达 next_change_point 时继续处理这个查询。我们将这个查询（带着它当前的 k 值 $k_q^{(l)}$）延迟到索引 next_change_point 处理。

5. 如何高效找到 next_change_point?:
   我们需要快速找到最小的 $t > l$ 使得 $a[t]$ 是当前 $k$ 值的因子。
   这等价于找到最小的 $t > l$ 使得 $a[t]$ 属于 $k$ 的因子集合 $D(k)$。
   我们可以预处理出每个数 $v$ 的所有因子（或质因子，但这里需要的是 $a[t]$ 本身）。
   对于每个可能的值 $v$ (从 2 到 $V=\max(k, a_i)$)，我们需要维护 $v$ 在数组 $a$ 中下一次出现的索引。

   • 我们可以使用一个数组 pos[v] 来存储值 v 在数组 $a$ 中当前扫描线位置之后的第一个出现位置。
   • 预处理: 从右向左扫描数组 $a$ (从 $n-1$ 到 0)。维护一个临时 last_pos 数组。对于每个 $i$，nxt[i] = last_pos[a[i]] (记录 $a[i]$ 在 $i$ 之后第一次出现的位置)，然后更新 last_pos[a[i]] = i。处理完后，将 last_pos 复制到 pos，此时 pos[v] 存储的是 $v$ 在整个数组中第一次出现的位置。
   • 扫描线更新: 当扫描线从 $l-1$ 移动到 $l$ 时，处理完所有与 $l$ 相关的查询后，我们需要更新 pos 数组。具体来说，pos[a[l]] 需要更新为 $a[l]$ 在 $l$ 之后第一次出现的位置，这个信息存储在 nxt[l] 中。pos[a[l]] = nxt[l]。

6. 算法实现细节:

   • 预计算因子: 使用类似筛法的方式，预计算 factors[v]，存储所有大于等于 2 的因子 d of v。时间复杂度 $O(V \log V)$。
   • 预计算 nxt 和 pos: 从右到左扫描 a，计算 nxt 数组和 pos 数组的初始状态。时间复杂度 $O(n)$。
   • 离线查询: 使用 vector<vector<int>> qry(n)，qry[l] 存储所有原始左端点为 l 或被延迟到 l 的查询的原始索引。
   • 存储查询状态: 使用 vector<i64> k(q) 存储每个查询当前 k 的值，vector<int> r(q) 存储每个查询的右端点 (使用 1-based 或调整为 0-based 结束点)，vector<i64> ans(q) 存储每个查询的累计答案。
   • 主循环 (扫描线): 遍历 l 从 0 到 n-1。
     1. 处理 qry[l] 中的每个查询 i：
        a. 获取当前查询的 k 值 k_current = k[i] 和右端点 r_current = r[i]。
        b. 模拟步骤 l: while (k_current % a[l] == 0) { k_current /= a[l]; }。
        c. 找到 next_change_point = $\min \{ \text{pos}[d] \mid d \in \text{factors}[k_\text{current}] \}$.
        d. 如果 next_change_point >= r_current:
        ans[i] += (i64)(r_current - l) * k_current;
        e. 如果 next_change_point < r_current:
        ans[i] += (i64)(next_change_point - l) * k_current;
        将查询 i 添加到 qry[next_change_point] 中。
        更新 k[i] = k_current (保存延迟处理时的 k 值)。
     2. 更新 pos: pos[a[l]] = nxt[l]。
   • 输出: 遍历 ans 数组并输出。

7. 复杂度再评估:

   • 预计算: $O(V \log V + n)$.
   • 扫描线: $O(n)$.
   • 查询处理: 每个查询 i 最多被处理 $O(\log k)$ 次（因为它最多改变 $k$ 值 $\log k$ 次）。每次处理涉及：
     • 因子分解（预计算了因子列表，查找因子数 $d(k)$）。
     • 查找 next_change_point（需要 $O(d(k))$ 次 pos 访问）。
     • while 循环除法 $O(\log k)$。
   • 总查询处理复杂度约为 $O(q \cdot \log k \cdot (d_{\max} + \log k))$。
   • 整体复杂度为 $O(V \log V + n + q \cdot \log k \cdot (d_{\max} + \log k))$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int V = 1E5; // 数值的最大范围 (a[i] 和 k)
constexpr int inf = 1E9; // 定义一个足够大的整数作为无穷大

// pos[v] 存储值 v 在扫描线当前位置之后的下一个出现位置
int pos[V + 1]; 
// factors[v] 存储 v 的所有大于等于 2 的因子
std::vector<int> factors[V + 1];

// 处理单个测试用例的函数
void solve() {
    int n, q; // 数组长度 n, 查询数量 q
    std::cin >> n >> q;

    // 存储数组 a
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    // k[i] 存储第 i 个查询当前的 k 值
    // r[i] 存储第 i 个查询的右端点 (1-based)
    std::vector<int> k(q), r(q); 
    // qry[l] 存储所有左端点为 l (或被延迟到 l) 的查询的原始索引
    std::vector<std::vector<int>> qry(n); 
    for (int i = 0; i < q; i++) {
        int l;
        std::cin >> k[i] >> l >> r[i];
        l--; // 转换为 0-based 左端点
        qry[l].push_back(i); // 将查询加入其初始左端点的列表
    }

    // ans[i] 存储第 i 个查询的累计答案
    std::vector<i64> ans(q);

    // nxt[i] 存储 a[i] 这个值在索引 i 之后下一次出现的位置
    std::vector<int> nxt(n, inf); 
    // 临时 pos 数组，用于从右向左计算 nxt 和 pos 的初始状态
    // std::fill(pos, pos + V + 1, inf); // 需要在 test case 内部重置 pos
    // 注意：全局 pos 在 solve 开始前被 fill 过，但在 test case 之间需要重置
    // 或者，在 test case 结束时恢复 pos 的状态（更复杂）
    // 更好的方法是在 solve 开始时 fill
    std::fill(pos, pos + V + 1, inf); // 重置 pos 数组

    // 从右向左预计算 nxt 数组和 pos 数组的初始状态
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = pos[a[i]]; // nxt[i] 是 a[i] 在 i 之后首次出现的位置
        pos[a[i]] = i;      // pos[a[i]] 更新为当前位置 i
    }
    // 此时，pos[v] 存储的是 v 在整个数组 a 中首次出现的位置

    // 扫描线从左到右处理
    for (int l = 0; l < n; l++) {
        // 处理所有当前需要从索引 l 开始处理的查询
        for (auto i : qry[l]) {
            // 模拟伪代码中索引 l 处的 while 循环
            while (k[i] > 0 && a[l] > 1 && k[i] % a[l] == 0) { // 增加 k[i]>0 和 a[l]>1 检查
                k[i] /= a[l];
            }

            // 查找下一个可能改变 k[i] 值的位置 t
            int t = inf; // 初始化为无穷大
            // 遍历当前 k[i] 的所有因子 d
            for (auto d : factors[k[i]]) {
                // 找到因子 d 在 l 之后首次出现的位置 pos[d]
                // 取所有这些位置中的最小值
                t = std::min(t, pos[d]); 
            }

            // 判断下一个改变点 t 是否在查询区间 [l, r[i]) 之外
            if (t >= r[i]) {
                // 如果在区间外，则从 l 到 r[i]-1，k 的值都等于当前的 k[i]
                // 累加贡献 (r[i] - l) * k[i]
                ans[i] += 1LL * (r[i] - l) * k[i];
            } else {
                // 如果在区间内，则从 l 到 t-1，k 的值等于当前的 k[i]
                // 累加贡献 (t - l) * k[i]
                ans[i] += 1LL * (t - l) * k[i];
                // 断言确保 t > l (否则逻辑有问题)
                assert(t > l); 
                // 将查询 i 延迟到索引 t 处理
                qry[t].push_back(i);
                // k[i] 的值保持当前值，传递给下一次处理
            }
        }
        // 当前索引 l 处理完毕，更新 pos[a[l]] 指向 a[l] 的下一个出现位置
        pos[a[l]] = nxt[l]; 
    }

    // 输出所有查询的答案
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }
}

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // --- 全局预计算 ---
    // 初始化 pos 数组（虽然在 solve 里也做了，这里做一次确保初始状态）
    std::fill(pos, pos + V + 1, inf); 
    // 预计算所有 V 以内数的因子（筛法）
    for (int i = 2; i <= V; i++) { // 从 2 开始，因为 a[i] >= 2
        for (int j = i; j <= V; j += i) {
            factors[j].push_back(i); // i 是 j 的一个因子
        }
    }
    // --- 预计算结束 ---

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve();
    }

    return 0; // 程序正常结束
}