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
说明
In the first query of the first sample you can multiply second number by 7 to get 259 and multiply the third one by 37 to get 1036. Then $ a_2 \cdot a_3 = 268\,324 = 518^2 $ .
In the second query subarray is already good because $ a_4 \cdot a_6 = 24^2 $ .
In the third query you can divide 50 by 2 to get 25. Then $ a_6 \cdot a_8 = 30^2 $ .