题目详情题解（0）讨论（0）提交记录（0）

AT_arc023_4.[ARC023D] GCD区间

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给出一个长度为 nn (1≤n≤105)(1\le n\le 10^{5}) 的序列和 mm (1≤m≤105)(1\le m\le 10^{5}) 个询问。对于每个询问，输入 xx (1≤x≤109)(1\le x\le 10^{9})，输出满足 gcd⁡(al,al+1,...,ar)=x\gcd(a_l,a_{l+1},...,a_r)=x 的 (i,j)(i,j) 的对数。

输入格式

第一行两个整数 n,mn,m。

接下来的 nn 行，为序列，序列中的元素 aia_i 满足 (1≤ai≤109)(1\le a_i \le 10^{9})。

最后 mm 行，为询问。

输出格式

输出 mm 行，每行一个整数，回答询问。

输入输出样例

  • 输入#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

说明/提示

null

输入解题思路，AI测评打分。不知道怎么写?

首页