#O. L3-2 GCD Ultra

传统题

1000ms

256MiB

当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 $n$ 的数组 $a=[a_1,a_2,\cdots ,a_n]$ 。

对数组进行多次查询，每次查询数组的一个连续区间 $[l,r]$ ，需要计算集合 $S=\bigcup_{i=l}^{r}{\left\{\text{gcd}_{j=i}^r{a_j}\right\}}$ 的大小。

注意： $\text{gcd}_{i=p}^{q}{a_i}$ 表示数组 $a$ 中 $a_p,a_{p+1},\cdots ,a_{q}$ 的最大公因数， $\bigcup_{i=p}^{q}{s_i}$ 表示集合 $s_p,s_{p+1},\cdots s_{q}$ 的并集。

第一行两个整数 $n,m\ (1\leq n,m\leq 6\times 10^5)$ 表示序列大小和询问次数。

第二行 $n$ 个整数表示 $a_i\ (1\leq a_i\leq 2^{31})$ 。

接下来 $m$ 行，每行两个正整数 $l,r\ (1\leq l\leq r\leq n)$ 表示询问。

共 $m$ 行，每行一个正整数表示答案。

6 3
1 2 3 4 5 6
1 3
2 4
1 6

2
2
2