正整数 \(x\) に対し \(f(x)\) を \(x\) の約数のうち最大の平方数とします。

\(i\times j\) が平方数になることは \(\displaystyle \frac i{f(i)}\times j\) が平方数となることと同値です。

\(\displaystyle d[i]=\frac i{f(i)}\) となるような配列 \(d\) を作成します。これはエラトステネスのふるいと同じ要領で平方数で割っていくことで実現できます。

\(i\) を固定して考えると、 \(i\times j\) が平方数となる \(j\) 、つまり \(d[i]\times j\) が平方数となる \(1\) 以上 \(N\) 以下の整数 \(j\) の個数は \(j\) が平方数となる \(1\) 以上 \(\displaystyle \frac N{d[i]}\) 以下の整数 \(j\) の個数と一致します。これは \(h[i]\) を \(i\) 以下の平方数の個数とした配列 \(h\) を作成することで求めることができます。

以上でこの問題が解けました。計算量は \(O(N)\) です。

実装例(Java)

import java.util.*;

class Main {
    public static void main(String args[]) {
        var sc = new Scanner(System.in);
        int n = sc.nextInt();
        var d = new int[n + 1];
        Arrays.setAll(d, i -> i);
        for (int i = 2; i * i <= n; i++) {
            if (d[i] != i)
                continue;
            int ii = i * i;
            for (int j = ii; j <= n; j += ii)
                while (d[j] % ii == 0)
                    d[j] /= ii;
        }
        var h = new int[n + 1];
        for (int i = 1; i * i <= n; i++)
            h[i * i]++;
        Arrays.parallelPrefix(h, Integer::sum);
        long ans = 0L;
        for (int i = 1; i <= n; i++)
            ans += h[n / d[i]];
        System.out.println(ans);
        sc.close();
    }
}