← 返回题目列表

AtCoder · arc023_4

D. GCD 部分

中文机器翻译题面 查看原题

問題文

高桥先生喜欢创建数字序列并对它们执行各种操作。我特别喜欢对区间进行各种运算,比如计算区间之和、区间最大公约数。

因此,高桥先生认为对于某个数列,区间的最大公约数是某个值。 我决定计算 x 的间隔数。 高桥用一个程序来解决这个问题,但他意识到数字序列越长,花费的时间就越多。

你的工作是为 Takahashi 编写一个程序,即使数字序列很长也能快速运行。 此外,作为奖励功能,同一数字序列会显示多个数字。 即使有 x 候选人,所有 我决定添加一个查询功能,以便我可以计算 x 。

你有长度 给出了 n 序列 有 A=\{a_1,a_2,..,a_n\} 。另外,查询数量 m 和 还给出了 x_1,x_2,..,x_m 。 每个 对于 x_i (1 ≦ i ≦ m) ,区间中包含的所有数字的最大公约数为 一个区间使得 x_i 请输出 [s,t] (1 ≦ s ≦ t ≦ n) 的编号。

例如,A=\{1,2,4\} ,最大公约数为1的区间为[1,1],[1,2],[1,3]最大公约数为 2 的区间为[2,2],[2,3] 最大公约数为 4 的区间为 仅[3,3] 。


入力

输入将以以下格式从标准输入给出。

n m
a_1
a_2
:
a_n
x_1
x_2
:
x_m
  • 1 行包含一个表示序列长度的整数。 n (1 ≦ n ≦ 100,000) 及查询次数 在 m (1 ≦ m ≦ 100,000) 用空格分隔。
  • 2 从行 n 行中,序列 给出了值 A。其中 i 行中的编号规则 代表每个 A 的 已知 i 值的整数 a_i (1 ≦ a_i ≦ 10^9) 给出。
  • n+2 从行 m 行给出您要检查的值。其中 行 i 在第 i 个查询中 代表 x 每个值的整数 x_i (1 ≦ x_i ≦ 10^9) 给出。

出力

从第一行开始按顺序回答每个问题。 输出 m 行。还在输出末尾添加换行符。


入力例1

3 4
1
2
4
1
2
3
4

出力例1

3
2
0
1

给出的数字序列来自问题文本。


入力例2

6 7
12
6
4
3
2
1
1
2
3
4
6
12
8

出力例2

13
3
1
1
2
1
0

入力例3

5 8
4
6
42
28
41
1
2
4
6
7
14
14
41

出力例3

4
4
1
2
0
1
1
1