E-寄CD?_2022广西师范大学暑期训练赛

时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小L 觉得构造题目背景真的太难了, 于是决定给你简化题面, 给你一个长度为 $n$ 的序列 $a$ , 接下来有 $m$ 个询问,

每个询问给出一个数 $x$ , 你需要求出 $gcd(a_l, a_{l+1}...a_r) = x$ 的区间数量

$gcd(a_l, a_{l+1},...a_r)$ 的意思是 $(((gcd(a_l, a_{l+1}), a_{l+2}),a....)a_r)$

小 第一行包含一个整数   , 表示测试数据的数量
第二行包含两个整数   分别表示序列长度和询问的数量
第三行包含  个整数, 表示序列  中的每个元素 
接下来  行, 每行一个整数

共  组数据, 每组数据共  行, 每行一个整数表示答案

示例1

复制

复制

11
1

对于样例1: 区间  的有:
区间  的有: 

这里是[1,5] 是指的区间, 也就是a1,a2,a3,a4,a5

示例2

复制

1
6 6
1 1 4 5 1 4
1
1
4
5
1
4

复制

示例3

复制

复制