[ARC023D] GCD区間

## 题意翻译 给出一个长度为 $n$ $(1<=n<=10^{5})$ 的序列和 $m$ $(1<=m<=10^{5})$ 个询问。对于每个询问，输入 $x$ $(1<=x<=10^{9})$，输出满足 $gcd(a_l,a_{l+1},...,a_r)=x$ 的 $(i,j)$ 的对数。 ## 输入格式 第一行两个整数 $n,m$。 接下来的 $n$ 行，为序列，序列中的元素 $a_i$ 满足 $(1<=a_i<=10^{9})$。 最后 $m$ 行，为询问。 ## 输出格式 输出 $m$ 行，每行一个整数，回答询问。

[problemUrl]: https://atcoder.jp/contests/arc023/tasks/arc023_4 高橋君は、数列を作って、それに関していろいろ操作を施すのが好きです。特に、区間の和や区間の最大公約数を計算したりといった区間に関していろいろ操作を施すのが大好きです。 そこで、高橋君は、ある数列に関して、区間の最大公約数がとある値 $ x $ となるような区間の数を数えることにしました。 高橋君は、プログラムを使ってこの問題を解いたのですが、長い数列になればなるほど、時間がとても掛かってしまうことに気づきました。 あなたの仕事は、高橋君のために、数列が長いときでも高速に動作するプログラムを書くことです。 また、オマケ機能として、同じ数列に対して、いくつか $ 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] $の3つであり、最大公約数が2となる区間は、$ [2,2],[2,3] $ の2つであり、 最大公約数が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) $ が与えられる。

それぞれの問い合わせに対する答えを順番に 1 行目から $ m $ 行出力せよ。出力の末尾にも改行をいれること。

3 4
1
2
4
1
2
3
4

3
2
0
1

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

13
3
1
1
2
1
0

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

4
4
1
2
0
1
1
1

### Sample Explanation 1 与えられる数列は、問題文中のものです。