305420: CF1028H. Make Square
Memory Limit:1024 MB
Time Limit:7 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Make Square
题意翻译
我们称一个数列$b$是“优秀的”,当且仅当存在 $b_i\times b_j(i<j)$是一个完全平方数。 给定一个数列$a$,每次询问使$a_l,a_{l+1},\cdots,a_{r-1},a_r$这个数列成为一个“优秀的”数列至少要进行几次操作,共$q$次询问。 每一次操作,你可以将数列中的任意一个数乘以/除以一个质数$p$(除法需要保证被除数能被整除)。题目描述
We call an array $ b_1, b_2, \ldots, b_m $ good, if there exist two indices $ i < j $ such that $ b_i \cdot b_j $ is a [perfect square](https://en.wikipedia.org/wiki/Square_number). Given an array $ b_1, b_2, \ldots, b_m $ , in one action you can perform one of the following: - multiply any element $ b_i $ by any prime $ p $ ; - divide any element $ b_i $ by prime $ p $ , if $ b_i $ is divisible by $ p $ . Let $ f(b_1, b_2, \ldots, b_m) $ be the minimum number of actions needed to make the array $ b $ good. You are given an array of $ n $ integers $ a_1, a_2, \ldots, a_n $ and $ q $ queries of the form $ l_i, r_i $ . For each query output $ f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i}) $ .输入输出格式
输入格式
The first line contains two integers $ n $ and $ q $ ( $ 2 \le n \le 194\,598 $ , $ 1 \le q \le 1\,049\,658 $ ) — the length of the array and the number of queries. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 5\,032\,107 $ ) — the elements of the array. Each of the next $ q $ lines contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i < r_i \le n $ ) — the parameters of a query.
输出格式
Output $ q $ lines — the answers for each query in the order they are given in the input.
输入输出样例
输入样例 #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