题目大意
给出一个长度为 $n$ 的序列 $a_1…a_n$，有 $m$ 个询问，每次询问给出 $l, r, k$，问 $a_l…a_r$ 中，有多少数的出现次数与 $k$ 互质。
$n, m \leq 5e4，1 \leq a_i, k \leq n$
时限 6s
题解
区间问题可以考虑莫队，可以维护一个桶 $t_i$ 表示有多少数的出现次数是 $i$。
但是统计答案不方便，要把整个桶扫一次。
于是设个阈值 $s=\sqrt n$。如果某个数在全局的出现次数 $>s$，就提取出来单独对每个询问做贡献，剩下的数就做莫队。