Make Square
Contest: AIM Tech Round 5 (rated, Div. 1 + Div. 2)
Difficulty rating: 2900
Tags: math

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.

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})$$$.

Input format:
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 format:
Output $$$q$$$ lines — the answers for each query in the order they are given in the input.

Constraints:
Time limit: 7.0 s
Memory limit: 1024.0 MB

Note:
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$$$.

Example input:
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

Example output:
2
0
1
3
0
1
1
1
0
0

Editorial:
Firstly, we can divide out all squares from the $$$a_i$$$, since they make no difference. Thus, each $$$a_i$$$ is then a product of unique primes. If we want to transform $$$a_i$$$ and $$$a_j$$$ so that their product becomes a square, the cost is the number of primes that appear in one but not in another. Each $$$a_i$$$ can have at most $$$7$$$ primes ($$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$$$ is too big), so at most $$$128$$$ divisors.
Sweep from left to right, maintaining $$$dp[val][dist]$$$ — the rightmost index $$$i$$$ so far that $$$a_i$$$ can be expressed as $$$val \cdot x$$$, where $$$x$$$ has $$$dist$$$ primes in its factorization. Also maintain $$$best[D]$$$ — the rightmost $$$l$$$ such that the answer for the segment $$$[l; i]$$$ is $$$D$$$, for current index $$$i$$$. To add a new $$$a_i$$$ in $$$dp$$$, consider each divisor $$$val$$$ in it, calculate $$$dist$$$ as the number of primes in $$$\dfrac{a_i}{val}$$$ and relax $$$dp[val][dist]$$$ with $$$i$$$. Before doing this for $$$i$$$, we need to update $$$best$$$ array: for each $$$val~|~a_i$$$ and $$$\dfrac{a_i}{val}$$$ having $$$dist$$$ primes in factorization and for each $$$k \le 7$$$ relax $$$best[k + dist]$$$ with $$$dp[val][dist]$$$. Then all queries with right border equal to $$$i$$$ can be answered in $$$O(M_{ans})$$$ time, where $$$M_{ans} \le 14$$$.
The complexity of this solution is $$$O(n \cdot M_{primes} \cdot 2^{M_{primes}} + q \cdot M_{ans})$$$, where $$$M_{primes} = 7$$$, $$$M_{ans} \le 2 M_{primes}$$$. Actually, the maximum possible answer for a query in this problem is $$$11$$$. You can find two numbers generating it as an exercise.