神奇的%系列二

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 131070/65535KB (Java/Others)

Problem Description

在计算机的世界里,%不是百分比,而是除法取余哟!

比如:
  4 % 2 = 0
  5 % 3 = 2

现在,给你 个正整数的序列,a[1],a[2]...a[i]...a[n]

Q 个询问:

L R X ,问下标区间在[L, R]之间的数a[i],有几个数能整除 X(即 X % a[i] == 0,且L ≤ i ≤ R

Input

输入有多组数据。(≤ 25)

对于每组数据:

第一行:N(表示 N 个元素,1 ≤ N ≤ 100000

第二行:a[1] a[2] ... a[n](表示序列的 N 个元素,1 ≤ a[i] ≤ 100000

第三行:Q(表示 个询问,1 ≤ Q ≤ 100000

接下来 Q 行,每行三个整数:L R X (1 ≤ L ≤ R ≤ N,1 ≤ X ≤ 100000)

Output

对于每个询问,输出一个数。

表示下标区间在[L, R]之间的数,有几个能整除 的数

Sample Input

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

Sample Output

2
2
5

Source

zju_xxx

Manager

Information
Solved Number87
Submit Number316
Problem Tags
binary search
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel