線形篩 を使うことで \(O(N)\) で解けます。

\(\gdef\lpf#1{\mathrm{lpf}(#1)}\gdef\dp{\mathrm{dp}}\) 線形篩を用いることで、前処理 \(O(N)\) 時間で、各 \(i\) (\(2\le i\le N\)) の最小素因数 \(\lpf{i}\) が \(O(1)\) 時間で求められます。

\(\dp[i]\) を「\(i\) の素因数のうち、指数部が奇数であるもの（の 1 乗）の積」とすると、

\[ \begin{aligned} \dp[1] &= 1; \\ \dp[i] &= \begin{cases} \dp[i/\lpf{i}] \div \lpf{i}, & \text{if }\dp[i/\lpf{i}]\bmod\lpf{i} = 0; \\ \dp[i/\lpf{i}] \times \lpf{i}, & \text{otherwise}. \end{cases} \end{aligned} \]

として求めることができます。

あとは、\(\dp[i]\) が共通であるものの個数を（\(\dp[i]\le N\) なので、配列を用いて \(O(N)\) 時間で）数え、その 2 乗和を答えればよいです。