假设值域为 \(v\) 即 \(10^5\)，显然每个质因数 \(p\) 独立，考虑计算每个 \(p\) 对答案的贡献。
\(p\) 对答案的贡献次数为 \(\sum\limits_{S\subseteq [l,r]}\min\limits_{i\in S}q_i\)，\(q_i\) 为 \(a_i\) 这个数的质因子 \(p\) 的次数。
然后你发现枚举每个集合太蠢了，考虑某个集合 \(S\) 对答案贡献了 \(q\) 的 \(\min\limits_{i\in S}q_i\) 次，所以 \(p\) 的贡献就是 \(\sum\limits_{i=1}^{∞}\left(2^{\sum\limits_{j=l}^{r}[q_j\ge i]}-1\right)\)，因为每个集合 \(S\) 都刚好在 \(i\in[1,\min\limits_{i\in S}q_i]\) 时各被算进了一次。
然后就很好做了吧，对于每个 \(a_i\) 进行 \(O(\sqrt v)\) 分解质因数，这一步是 \(O(n\sqrt v)\) 的。
根号分治。对于满足 \(p\le \sqrt v\) 的质数，可以暴力前缀和预处理 \(s_{i,j,p}\) 代表 \(k\in[1,i]\) 这段区间内，使得 \(a_k\) 是 \(p^j\) 的倍数的 \(k\) 的个数。毛估估一下 \((j,p)\) 中满足 \(p^j\le \sqrt v\) 的数对大概在 \(t=180\) 左右，所以应该是跑得了的，复杂度 \(O(tn)\)。
\(O(n\sqrt v)\) 预处理 \(f_{p,k}=p^{2^{k}-1}\)，一次查询 \([l,r]\) 的时候贡献就是 \(p^{\sum\limits_{j}{2^{s_{r,j,p}-s_{l-1,j,p}}-1}}\)，枚举 \(j,p\) 即可 \(O(t)\) 处理 \(p\le \sqrt v\) 的质因数贡献。
而满足 \(p> \sqrt v\) 的质数呢，对于每个数 \(a_i\)，肯定有不超过一个这样的质因数。所以 \(p\) 的贡献次数即为包含 \(p\) 作为公约数的 \([l,r]\) 中的子集个数，即 \(\sum\limits_{i=1}^{∞}\left(2^{\sum\limits_{j=l}^{r}[q_j\ge i]}-1\right)\) 中只有 \(i=1\) 的时候有贡献。
然后我们就可以进行一个类似区间数颜色的莫队了。同样预处理 \(p^{2^k-1}\) 的值及其逆元（因为要撤销）即可。需要注意的是对于每个 \(p\)，它的 \(k\) 只用预处理到 \(a\) 序列中 \(p\) 的出现次数，显然这是 \(O(n)\) 的。做完了。
复杂度 \(O(n(\sqrt w+\sqrt m+t)+m\sqrt w)\)，可过。