\(i\) を固定したとき、\(j\) の候補がいくつあるか求めることを考えます。
\(i\times k\) が平方数となるような最小の \(k\) は、\(i\) を平方数で割れるだけ割って残った数になります。\(i\times j\) が平方数となるような \(j\) は \(k\) に平方数を掛けたものに限り、また全てその形で表せます。(証明略)
それぞれのパートは愚直に計算することで \(i\) ごとに \(O(\sqrt{N})\) で \(j\) を全て求めることができ、全体で \(O(N^{1.5})\) でこの問題が解けます。

実装例(C)

#define ll long long
int main(){
	int n;
	scanf("%d",&n);
	ll ans=0;
	for(ll i=1;i<=n;i++){
		ll k=i;
		for(ll d=2;d*d<=k;d++){
			while(k%(d*d)==0)k/=d*d;
		}
		for(ll d=1;k*d*d<=n;d++)ans++;
	}
	printf("%lld",ans);
}