Preparing NOJ

SevenFireflie has a sequence of positive integers with a length of $$$n$$$ and quickly calculates all the factors of each number. In order to exercise his factor calculation ability, he has selected $$$q$$$ consecutive subsequences from the sequence and found a positive integer $$$p$$$ greater than $$$1$$$ for each subsequence, so that $$$p$$$ can divide as many numbers in this subsequence as possible. He has also found that $$$p$$$ may have more than one.

So the question is, how many numbers in each subsequence can be divided at most?

The first line contains an integer $$$T$$$ ($$$1 \le T \le 5 \times 10 ^ 4$$$), indicating that there is $$$T$$$ test cases next.

The first line of each test cases has two positive integers $$$n$$$ ($$$1\le n\le 5\times10^4$$$), $$$q$$$ ($$$1\le q\le 5\times10^4$$$).

Next line $$$n$$$ integers $$$a_i$$$ ($$$1\le i\le n,1\le a_i\le 1\times10^6$$$), which representing the numbers in this sequence. The two adjacent numbers are separated by a space.

Each of the next $$$q$$$ lines contains two integers $$$l,r$$$ ($$$1\le l\le r\le n$$$), representing a subsequence being queried, $$$a_l, a_{l+1}, \cdots, a_r$$$, and $$$l,r$$$ are separated by a space.

The input guarantees that the sum of $$$n$$$ does not exceed $$$5\times10^4$$$ and the sum of $$$q$$$ does not exceed $$$5\times10^4$$$.

For each test case, output $$$q$$$ lines, each line contains a positive integer, indicating the answer.

1 10 5 20 15 6 1 21 12 2 3 17 9 1 4 2 5 3 6 4 7 5 10

2 3 3 2 4

Info

Provider CodeForces Gym

Origin 2021 Jiangxi Provincial Collegiate Programming Contest

Code GYM103366G

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:31:57

Related