まず，\(Q_j\) が \(P_i\) の倍数となっている，という \((i,j)\) のペアを列挙してみます． このようなペアの個数はおおよそ \(\sum_{1 \leq i \leq N}N/i\) であり，これは \(O(N \log N)\) であることが知られています．

この問題は，そのようなペアの列 \((i_1,j_1),(i_2,j_2),\cdots,(i_k,j_k)\) であって，\(i_1 < i_2 < \cdots < i_k\), \(j_1 < j_2 < \cdots < j_k\) を満たすものを考え，その長さを最大化することです．

列挙したペアを \((i,-j)\) をキーにして（\(j\) の符号が反転していることに注意）ソートしてみます． そうして得られた列の \(j\) だけを見て，これの最長（狭義単調）増加部分列を求めると，これが元の問題の答えになっていることがわかります． （同じ \(i\) に対応する \(j\) が降順に並ぶようになっているため，\(i\) 狭義単調増加であることが保証される）

最長増加部分列は配列に対する lower_bound を使うと簡単に実装できます． 計算量は全体で \(O(N\log^2 N)\) 時間になります．

解答例(pypy3)