How I came up to the solution during the contest:

• We are interested in pairs $$$(a_i, b_i)$$$ where $$$b_i$$$ is a multiple of $$$a_i$$$. There are $$$O(n \log n)$$$ such pairs.
• For each pair $$$(a_i, b_i)$$$ with $$$i \geq 2$$$, $$$a_{i-1} < a_i$$$ and $$$b_{i-1} < b_i$$$. So, the maximum length of a subsequence that finishes with $$$(a_i, b_i)$$$ is $$$1\phantom{'}+ $$$ the maximum length of a subsequence that finishes with any valid $$$(a_{i-1}, b_{i-1})$$$. We are calculating lengths using previous lengths, so let's use DP.
• While calculating the DP, we have to guarantee $$$a_{i-1} < a_i$$$ and $$$b_{i-1} < b_i$$$. The first condition can be handled by considering the $$$a_i$$$ in increasing order. The second condition can be handled by using any data structure that calculates the maximum $$$x_i$$$ in a prefix (i.e. $$$1 \leq i \leq p$$$) and supports point updates. The simpler one is Fenwick tree.

I actually didn't realize this is a LIS during the contest, but you could notice that while handling the second condition (i.e., after considering $$$a_i$$$ in increasing order, the $$$b_i$$$ should be increasing and as many as possible, so it's a LIS).