正键则整

区间比较复杂，我们直接考虑只有一个点的情况 我们可以考虑“多少种情况的最大公约数=k” 注意到有以下情况

$$\begin{cases} 全是k \\ 全是k的倍数 \end{cases} \rightarrow \forall x\in[1,m),x = kt, t\in N^*$$

x又有多少种呢？

答案是显然的 $\lfloor \frac{m}{k} \rfloor$

因为又有n种位置可以放，所以 定义$f(x)$表示该数组的最大公约数为$x$的时候的方案数

$$\text{f}(k) = (\lfloor \frac{m}{k} \rfloor)^n$$

（? …… ?）Katex太难写了，呜呜呜呜呜

但是这上面的只是粗略的计算！！！！

我们注意到会有更多的k的倍数为最大公约数的情形也被包含进去了(eg:2k, 3k, 4k) 大约就是这种情况（我先暂时的设置常数$p$）

$$\begin{cases} 全是kp \\ 全是kp的倍数 \end{cases} \Rightarrow \forall x \in [1,m), x = kpt 且p,t \in N^*$$

非常简单，直接在计算$f(x)$的时候从m为最大公约数开始到1倒序计算，然后直接减去前面的f(px)即可

最后的答案就是

$$\sum_{i = l}^{r} = f(i)$$

我在考试的时候写的这个赛时思路，这个Latex好折磨人啊为！！！ (#`O′)