Familiar Operations
Contest: Technocup 2019 - Elimination Round 2
Difficulty rating: 2800
Tags: brute force, graphs, math

You are given two positive integers $$$a$$$ and $$$b$$$. There are two possible operations:

1. multiply one of the numbers by some prime $$$p$$$;
2. divide one of the numbers on its prime factor $$$p$$$.

What is the minimum number of operations required to obtain two integers having the same number of divisors? You are given several such pairs, you need to find the answer for each of them.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of pairs of integers for which you are to find the answer.

Each of the next $$$t$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$).

Output format:
Output $$$t$$$ lines — the $$$i$$$-th of them should contain the answer for the pair $$$a_i$$$, $$$b_i$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
These are the numbers with equal number of divisors, which are optimal to obtain in the sample test case:

- $$$(27, 10)$$$, 4 divisors
- $$$(100, 1156)$$$, 9 divisors
- $$$(220, 140)$$$, 12 divisors
- $$$(17, 19)$$$, 2 divisors
- $$$(12, 18)$$$, 6 divisors
- $$$(50, 32)$$$, 6 divisors
- $$$(224, 1925)$$$, 12 divisors

Note that there can be several optimal pairs of numbers.

Example input:
8
9 10
100 17
220 70
17 19
4 18
32 20
100 32
224 385

Example output:
1
3
1
0
1
0
1
1

Editorial:
Note that if $$$a = \prod\limits_{i=1}^{k} p_i ^ {x_i}$$$ then $$$d(a) = \prod\limits_{i=1}^{k}(x_i+1)$$$. This implies that we can map $$$a$$$ to vector $$$(x_1, x_2, \ldots, x_k)$$$, where $$$x_1 \ge x_2 \ge \ldots \ge x_k$$$, because the order of the powers doesn't matter. The operations correspond to adding 1 to some item or appending 1 to the end of the vector or decreasing 1 from some item and sorting the vector after that, erasing zeros. There are only 289 different such vectors for numbers up to $$$10^6$$$, so we need to calculate only 41616 distances.
The first thought could be to just run Floyd-Warshall algorithm on these 289 vertices, which would fit in time. After that for each pair $$$(x, d)$$$ we can find the minimum number of operations needed to make with vector $$$x$$$ so that the generated number has $$$d$$$ divisors. To find the answer for $$$(x, y)$$$, we could simply iterate over all possible values of $$$d$$$. But there are some tricky cases. For example, for numbers $$$2^{19}$$$ and $$$2^2 3^6$$$ the answer is 1, because after multiplying the first number by 2 both numbers have 21 divisors. But the number $$$2^{20} > 10^6$$$, and the vector $$$(20)$$$ is not among these 289 vertices. So, we need to consider some other vectors too.
Anyway, let's run this algorithm to see what could be the maximal distance between the two numbers up to $$$10^6$$$. It turns out that in 10 operations any two numbers can be led to have the same number of divisors when all numbers in the path don't exceed $$$10^6$$$ too.
This means that each possible number in the optimal path satisfies $$$\sum\limits_{i=1}^{k} x_i < 30$$$, because for the numbers in the input this sum doesn't exceed 19, and there can be no more than 10 operations with each number. This condition gives us all vectors of powers necessary to consider as middle points for the pairs which can be in the input. There are 28629 such vectors. Now we run 289 bfs instances on the generated graph with the start in each possible vector from the input and build the same data structure for pairs $$$(x, d)$$$ as explained before, which allows us to find the answers for all vectors of numbers up to $$$10^6$$$.
This solution works in 2.5s on cf servers, which is still too slow. But the thing is that we found answers for all pairs of the vectors from the input. So we can try to get rid of some unnecessary vertices and simply check if the sum of answers is unchanged. One of the possible speedups is to consider only vectors generating the number of divisors not more than some reasonable number. The maximum number of divisors of some necessary vector is 288, so magic constants like 300 or more will work. Another possible speedup is to decrease the border on the sum of powers from 30 to 22, which is precise.