现有 $q$ 个询问，每个询问给出 $k, l, r$，要求计算 $f(k, a, l, r)$。

总限制：$\sum n \le 10^5$，$\sum q \le 5\times 10^4$。

直接按伪代码模拟每次询问复杂度 $O((r-l+1) \cdot \log k)$，最坏 $O(nq)$，不可接受，需要更高效的算法。

核心观察

1. $k$ 何时变化？

伪代码中的 while 循环只在 $a[i]$ 整除当前 $k$ 时执行除法操作。因此 $k$ 仅在遇到它的某个约数时才会改变。

2. 每个约数最多触发一次变化

假设 $d$ 是 $k$ 的一个约数。在区间 $[l, r]$ 中第一次出现 $a[i] = d$ 时，内层 while 会将 $k$ 中所有因子 $d$ 除尽。之后 $k$ 不再被 $d$ 整除，因此后续再遇到 $a[j] = d$ 时，while 条件不成立，$k$ 不变。

结论：在一次询问 $[l, r]$ 中，$k$ 的变化次数 $\le$ $k$ 的约数个数 $d(k)$。

在 $k \le 10^5$ 范围内，$d(k)$ 最大值约为 $128$（当 $k=83160$ 等），实际平均更小（约 $\sqrt[3]{k}$ 量级）。因此我们可以在每次询问时只关心那些 第一次出现 的约数位置。

3. 未变化的段贡献

如果 $k$ 在位置 $i$ 和下一个变化位置 $j$ 之间保持不变，那么这段的子数组对答案的贡献就是 $k \times (j - i)$。因此，我们只要找出 $k$ 依次变化的那些位置和当时的值，即可分段累加。

算法设计

预处理：记录每个值的出现位置

使用映射（或静态数组，因 $a_i \le 10^5$）pos[x] 存储值 $x$ 在数组 $a$ 中所有出现的下标（升序）。C++ 中可用 map<int, vector<int>> 或全局 vector<int> pos[100001]。

查询处理步骤

对询问按 左端点 $l$ 排序，这样我们可以随着 $l$ 的向右移动，维护一个 指针数组 ptr[x]，表示在当前位置之前，值 $x$ 已经出现过多少次。换句话说，对于当前询问的 $l$，pos[x][ptr[x]] 就是 $x$ 在 $[l, n]$ 中第一次出现的位置（若该下标 $\le r$ 且 ptr[x] 未越界）。

过程：

1. 将所有询问按 $l$ 升序排序。
2. 维护一个变量 prevL，初始为 $1$。对于每个询问 $(k, l, r)$：
   • 将 prevL 到 $l-1$ 之间的元素从“可用集合”中移除，即对每个 $a[j]$ 将其对应的 ptr[a[j]] 加 $1$，表示该值的下一次出现需要看下一个下标。
   • 更新 prevL = l。
3. 对当前 $k$，枚举其所有约数。对于每个约数 $d > 1$：
   • 检查 pos[d] 是否非空、ptr[d] 是否未越界、且 pos[d][ptr[d]] <= r。
   • 若满足，说明 $d$ 在 $[l, r]$ 内首次出现，记录该位置和值。
4. 将记录的所有“变化点”按位置从小到大排序。
5. 从 $l$ 开始，依次用当前 $k$ 乘以区间长度累加到答案，遇到变化点时用约数除尽 $k$，继续处理。

注意：如果没有任何约数在区间内出现，则整个区间内 $k$ 不变，答案为 $k \times (r-l+1)$。

复杂度分析

• 枚举约数：$O(\sqrt{k})$（或通过预处理的约数表 $O(1)$ 获取所有约数）。
• 每个询问的约数检查：$O(d(k) \log n)$（若用二分查找首次出现位置，但标准程序利用指针保证了 O(1) 定位）。
  标准程序用指针数组 ptr，对于每个值可以直接取 pos[val][ptr[val]]，无需二分，故每次检查是 $O(1)$ 的。
• 排序变化点：$O(d(k) \log d(k))$，由于 $d(k)$ 很小，可以视为常数。
• 查询的预处理移动 ptr：每个元素恰好被“跳过”一次，总复杂度 $O(n)$。

因此总复杂度为 $O(n + \sum (\sqrt{k} + d(k) \log d(k)))$，在数据范围内很快。若进一步预处理约数表，可以去掉 $\sqrt{k}$ 部分。

标准程序详解

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    map<int, vector<int>> pos;   // 值 -> 所有出现位置
    map<int, int> ptr;           // 值 -> 当前可用位置的索引
    int n, q; cin >> n >> q;
    int arr[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        pos[arr[i]].push_back(i);
        ptr[arr[i]] = 0;         // 初始指向第一个位置
    }

    // 读入询问，存储为 tuple (l, r, k, 原序号)
    vector<tuple<int, int, int, int>> qr(q);
    int c = 0;
    for (auto &[l, r, v, i] : qr) {
        cin >> v >> l >> r;
        i = c++;
    }
    vector<int> anss(q);
    sort(qr.begin(), qr.end());  // 按左端点 l 排序

    int prevL = 1;
    for (auto [l, r, v, idd] : qr) {
        // 移动左边界：丢弃 prevL 到 l-1 的元素
        for (int j = prevL; j < l; j++) {
            ptr[arr[j]]++;       // 该值下一次出现在下一个索引
        }
        prevL = l;

        // 找 v 的所有约数（>1）在区间内的首次出现
        vector<pair<int, int>> facts; // (位置, 约数)
        for (int i = 1; i * i <= v; i++) {
            if (v % i == 0) {
                int fact1 = v / i;
                if (!(pos[fact1].size() == 0 || ptr[fact1] >= pos[fact1].size() ||
                      pos[fact1][ptr[fact1]] > r || fact1 == 1)) {
                    facts.push_back({pos[fact1][ptr[fact1]], fact1});
                }
                int fact2 = i;
                if (fact2 == fact1) continue;
                if (!(pos[fact2].size() == 0 || ptr[fact2] >= pos[fact2].size() ||
                      pos[fact2][ptr[fact2]] > r || fact2 == 1)) {
                    facts.push_back({pos[fact2][ptr[fact2]], fact2});
                }
            }
        }

        sort(facts.begin(), facts.end()); // 按位置排序

        int pr = l;      // 当前段的起始位置
        int ans = 0;
        for (auto [idx, val] : facts) {
            int rr = idx - pr;             // 不变段长度
            ans += v * rr;                 // 累加当前 v 的贡献
            while (v % val == 0) v /= val; // 在 idx 处 v 发生变化
            pr = idx;
        }
        // 处理最后一段
        if (facts.empty()) ans = v * (r - l + 1);
        else ans += (r - pr + 1) * v;

        anss[idd] = ans;
    }

    for (int i = 0; i < q; i++) cout << anss[i] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}