← 返回题目列表

Codeforces · 1718/F

F. Burenka,数组和查询

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

Eugene 为 Burenka 准备了一个数组 $$$a$$$,长度为 $$$n$$$,整数从 $$$1$$$ 到 $$$m$$$ 为她的生日礼物。 Burenka 知道尤金真的很喜欢互质整数(整数 $$$x$$$ 和 $$$y$$$ 使得它们只有一个公因数(等于 $$$1$$$)),所以她想问尤金 $$$q$$$ 有关现在的问题。

每次 Burenka 都会选择数组 $$$a$$$ 的一个子段 $$$a_l, a_{l + 1}, \ldots, a_r$$$,并计算这些数字的乘积 $$$p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r$$$。然后她会要求尤金计算 $$$1$$$ 到 $$$C$$$ 之间与 $$$p$$$ 互质的整数的数量。

帮助尤金回答所有问题!

输入

输入的第一行有四个整数 $$$n$$$, $$$m$$$, $$$C$$$, $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$, $$$1 \leq m \leq 2\cdot 10^4$$$, $$$1 \leq C \leq 10^5$$$) — 数组 $$$a$$$ 的长度、$$$a_{i}$$$ 的最大可能值、值 $$$C$$$ 以及查询数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq m$$$) — 数组 $$$a$$$ 。

在接下来的 $$$q$$$ 行中给出了查询。每个查询由两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) 组成。

输出

打印 $$$q$$$ 整数——Burenka 查询的答案。

示例

输入 #1

5 5 5 3
1 2 3 2 5
1 1
2 4
4 5

输出 #1

5
2
2

注意

以下是示例的解释:

1. 在第一个查询中,乘积等于 $$$1$$$,它与 $$$1,2,3,4,5$$$ 互质。
2. 在第二个查询中,乘积等于 $$$12$$$,它与 $$$1$$$ 和 $$$5$$$ 互质。
3. 在第三个查询中,乘积等于 $$$10$$$,它与 $$$1$$$ 和 $$$3$$$ 互质。