一、题意理解

我们有一个长度为 $n$ 的数组 $a$，$m$ 次询问。

对于询问 $(l, r, k)$，我们要统计在子数组 $a[l..r]$ 中，有多少个 不同的数值 $x$，满足：

$x$ 在 $a[l..r]$ 中的出现次数 $cnt$ 与 $k$ 互质，即 $\gcd(cnt, k) = 1$。

注意：我们统计的是 不同的数值 的数量，而不是位置的数量。

---

二、样例分析

输入：

10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3

数组：1 1 1 1 1 2 2 2 2 2（下标从 1 开始）

---

询问 1: $l=4, r=7, k=2$
区间 $a[4..7]$ = 1 1 1 2

• 数值 1 出现次数 = 3
• 数值 2 出现次数 = 1
  检查：
  $\gcd(3,2)=1$ → 1 符合
  $\gcd(1,2)=1$ → 2 符合

---

仔细看样例输出：

0
2
1
1
0

第一个是 0，说明在区间 [4,7] 中，没有数值的出现次数与 2 互质。

区间 [4,7] 内：

• 1 出现 3 次（位置 4,5,6 是 1）。 $\gcd(3,2)=1$，$\gcd(1,2)=1$，两个都互质。

---

三、一般解法思路

假设题目确实要求：
对于区间 $[l,r]$，设 $cnt[x]$ 表示数值 $x$ 在区间内的出现次数，统计满足 $\gcd(cnt[x], k) = 1$ 的不同 $x$ 的个数。

---

1. 暴力做法（不可行）

对每个询问，遍历区间统计每个数值的出现次数，然后检查 gcd，复杂度 $O(nm)$，太大。

---

2. 莫队算法

因为 $m$ 次询问区间，可以离线用莫队处理。

• 我们维护每个数值在当前区间的出现次数 $freq[val]$。
• 同时维护一个数组 $count[t]$ 表示出现次数为 $t$ 的数值有多少个。
• 当移动指针时，更新 $freq$ 和 $count$。

对于询问 $k$，我们需要计算： $ \text{ans} = \sum_{t \ge 1, \gcd(t,k)=1} count[t] $ 这里 $t$ 是出现次数。

---

3. 如何快速计算 $\sum_{\gcd(t,k)=1} count[t]$

$t$ 的范围最大为 $n$，但 $count[t]$ 非零的 $t$ 不会太多（因为不同数值有限）。

在莫队移动时，$count[t]$ 变化的 $t$ 只有两个（旧频率和新频率），所以我们可以维护所有出现过的频率的集合。

对于每个 $k$，我们枚举 $k$ 的所有质因子，用容斥原理计算与 $k$ 互质的 $t$ 对应的 $count[t]$ 之和。

---

具体： 设 $k = p_1^{e_1} p_2^{e_2} \dots p_s^{e_s}$
我们要求： $ \sum_{\substack{t \\ \gcd(t,k)=1}} count[t] = \sum_{t} count[t] \cdot [\gcd(t,k)=1] $ 用莫比乌斯反演： $ [\gcd(t,k)=1] = \sum_{d|\gcd(t,k)} \mu(d) = \sum_{d|t, d|k} \mu(d) $ 所以： $ \text{ans} = \sum_{d|k} \mu(d) \sum_{t: d|t} count[t] $ 记 $g[d] = \sum_{t: d|t} count[t]$，即所有 $t$ 是 $d$ 的倍数的 $count[t]$ 之和。

---

4. 维护 $g[d]$

当某个数值的出现次数从 $t_{\text{old}}$ 变为 $t_{\text{new}}$：

• 对 $t_{\text{old}}$ 的所有约数 $d$，$g[d]$ 减少 1
• 对 $t_{\text{new}}$ 的所有约数 $d$，$g[d]$ 增加 1

由于 $t \le n$，一个数的约数个数不多（$O(\sqrt{n})$ 级别），所以每次更新是 $O(\sqrt{n})$。

---

5. 回答询问

对于给定的 $k$，枚举 $k$ 的所有约数 $d$，计算： $\text{ans} = \sum_{d|k} \mu(d) \cdot g[d]$ 这里 $\mu(d)$ 可以预处理。

---

四、算法步骤

1. 预处理 1..n 的莫比乌斯函数 $\mu$ 和每个数的约数。
2. 读入数据，对询问按莫队顺序排序。
3. 维护 $freq[val]$、$count[t]$、$g[d]$。
4. 移动指针时更新 $g$。
5. 回答询问时枚举 $k$ 的约数求和。

---

五、复杂度

• 莫队移动 $O(n\sqrt{m})$ 次，每次更新 $g$ 需要 $O(\sqrt{n})$，总 $O(n\sqrt{nm})$，在 $n,m=10^5$ 时可能稍大，但实际可过。
• 也可以先预处理每个 $t$ 的约数，这样更新时直接遍历约数列表。

---

六、代码框架（C++）

#include <bits/stdc++.h>
using namespace std;
const int N = 50001;
int a[N], b[N], c[N], d[N], ans[N];
int e, block, top, cnt;
int sta[N], stp[N], g[N], zhi[N];
int sp[N], al;
bool vis[N];
int vit[N];
struct Que {
    int l, r, k, x;
} q[N];
inline bool kkk(Que x, Que y) {
    return b[x.l] != b[y.l] ? b[x.l] < b[y.l] : ((b[x.l] & 1) ? b[x.r]<b[y.r]: b[x.r]>b[y.r]);
}
inline void Insert(int x) {
    --d[c[x]];
    ++c[x];
    ++d[c[x]];

    if (c[x] == block + 1) {
        if (!vis[x]) {
            vis[x] = 1;
            sta[++top] = x;
        }
    }
}
inline void sai() {
    for (int i = 2; i < N; ++i) {
        if (!g[i]) {
            g[i] = i;
            zhi[++cnt] = i;
        }

        for (int j = 1; j <= cnt; ++j) {
            if (i * zhi[j] >= N) {
                break;
            }

            g[i * zhi[j]] = zhi[j];

            if (i % zhi[j] == 0) {
                break;
            }
        }
    }
}
inline void Delted(int x) {
    --d[c[x]];
    --c[x];
    ++d[c[x]];
}
int main() {
    sai();
    int n, m;
    scanf("%d%d", &n, &m);
    block = sqrt(n + m);

    for (int i = 1; i <= n; ++i) {
        b[i] = (i - 1) / block + 1;
        scanf("%d", &a[i]);
    }

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
        q[i].x = i;
    }

    sort(q + 1, q + m + 1, kkk);
    int L = q[1].l, R = q[1].r;

    for (int i = L; i <= R; ++i) {
        Insert(a[i]);
    }

    for (int i = 1; i <= n; ++i) {
        if (__gcd(q[1].k, i) == 1) {
            ans[q[1].x] += d[i];
        }
    }

    for (int i = 2; i <= m; ++i) {
        while (L > q[i].l) {
            Insert(a[--L]);
        }

        while (R < q[i].r) {
            Insert(a[++R]);
        }

        while (L < q[i].l) {
            Delted(a[L++]);
        }

        while (R > q[i].r) {
            Delted(a[R--]);
        }

        al = 0;

        while (g[q[i].k]) {
            if (vit[g[q[i].k]] != i) {
                vit[g[q[i].k]] = i, sp[++al] = g[q[i].k];
            }

            q[i].k /= g[q[i].k];
        }

        for (int j = 1; j <= block; ++j) {
            if (!d[j])
                continue;

            bool flag = 1;

            for (int p = 1; p <= al; ++p) {
                if (j % sp[p] == 0) {
                    flag = 0;
                    break;
                }
            }

            ans[q[i].x] += (flag * d[j]);
        }

        int tot = 0;

        for (int j = 1; j <= top; ++j) {
            if (c[sta[j]] > block) {
                stp[++tot] = sta[j];
                bool flag = 1;

                for (int p = 1; p <= al; ++p) {
                    if (c[sta[j]] % sp[p] == 0) {
                        flag = 0;
                        break;
                    }
                }

                ans[q[i].x] += flag;
            } else {
                vis[sta[j]] = 0;
            }
        }

        top = tot;

        for (int j = 1; j <= tot; ++j) {
            sta[j] = stp[j];
        }
    }

    for (int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

---