← 返回题目列表

Codeforces · 1028/H

H. 做正方形

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

如果存在两个索引 $$$i < j$$$ 使得 $$$b_i \cdot b_j$$$ 是一个完全平方数,我们称数组 $$$b_1, b_2, \ldots, b_m$$$ 为好。

给定一个数组 $$$b_1, b_2, \ldots, b_m$$$,在一个操作中您可以执行以下操作之一:

- 任意元素 $$$b_i$$$ 乘以任意素数 $$$p$$$;
- 如果 $$$b_i$$$ 可被 $$$p$$$ 整除,则任何元素 $$$b_i$$$ 除以质数 $$$p$$$。

令 $$$f(b_1, b_2, \ldots, b_m)$$$ 为使数组 $$$b$$$ 良好所需的最小操作数。

给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$q$$$ 形式的查询 $$$l_i, r_i$$$。对于每个查询输出 $$$f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 194\,598$$$, $$$1 \le q \le 1\,049\,658$$$) — 数组的长度和查询的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5\,032\,107$$$) — 数组的元素。

接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — 查询的参数。

输出

输出 $$$q$$$ 行 — 每个查询的答案按照输入中给出的顺序排列。

示例

输入 #1

10 10
34 37 28 16 44 36 43 50 22 13
1 3
4 8
6 10
9 10
3 10
8 9
5 6
1 4
1 7
2 6

输出 #1

2
0
1
3
0
1
1
1
0
0

注意

在第一个样本的第一个查询中,您可以将第二个数字乘以 7 得到 259,将第三个数字乘以 37 得到 1036。然后 $$$a_2 \cdot a_3 = 268\,324 = 518^2$$$。

在第二个查询子数组中已经很好了,因为 $$$a_4 \cdot a_6 = 24^2$$$。

在第三个查询中,您可以将 50 除以 2 得到 25。然后 $$$a_6 \cdot a_8 = 30^2$$$。