\(O(N \sqrt{N\log N \log\log N})\) の解法を説明します。C/C++などの高速な言語を用いることで実行時間制限にギリギリ間に合わせることができます。

元の問題を解くには、次の問題が解ければ良いです。
「\(k=2,3,\ldots,N\) の全てについて、次の問題を解け：『\(\gcd(i,j)=k\) かつ \(\gcd(P_i,P_j)\neq 1\) となる \((i,j)\) の個数を求めよ』」

これは約数包除原理を用いることで、次の問題が解ければ十分です。
「\(k=2,3,\ldots,N\) の全てについて、次の問題を解け：『\(\gcd(i,j)\) が \(k\) の倍数かつ \(\gcd(P_i,P_j)\neq 1\) となる \((i,j)\) の個数を求めよ』」

『』の中はさらに次のように読み替えられます。
『indexが \(k\) の倍数である要素 \(P_k,P_{2k},\ldots\) の中に、gcdが \(2\) 以上になる組は何個あるか？』

この問題は次の2通りの方法で解くことができます。

• 愚直全探索により \(O((N/k)^2\log N)\)
• gcd畳み込みにより \(O(N\log\log N)\)

\(k\) の値によってこの2つのうち計算量が良い方を使って計算すると、冒頭の計算量を達成できます。