First, let us list all pairs \((i,j)\) such that \(Q_j\) is a multiple of \(P_i\). There are approximately \(\sum_{1 \leq i \leq N}N/i\) such pairs, which is known to be \(O(N \log N)\).

The problem considers a sequence of such pairs \((i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\) such that \(i_1 < i_2 < \cdots < i_k\), \(j_1 < j_2 < \cdots < j_k\) and asks us to maximize its length.

Let us sort the pairs using \((i,-j)\) as the key (note that the sign of \(j\) is inverted). In the resulting sequence, if we look only at \(j\)’s and find the longest (strictly) increasing subsequence, it turns out to be the answer to the original problem. (Since \(j\)’s corresponding to the same \(i\) are in descending order, the \(i\)’s in the subsequence are guaranteed to be strictly increasing.)

Implementation of finding the longest increasing subsequence can be easily done using the lower_bound on arrays. The total complexity will be \(O(N\log^2 N)\).

Sample Solution(pypy3)