整数 \(N\) の約数のうち、最大の平方数を \(f(N)\) と置きます。

ここで、整数 \(i,j\) に対して \(i \times j\) が平方数となることは \(\frac{i \times j}{f(i) \times f(j)}\) が平方数となることと同値です。

\(\frac{i}{f(i)}\) がある素数 \(p\) で \(2\) 回以上割り切れることはないため、\(\frac{i \times j}{f(i) \times f(j)}\) が平方数となることは \(\frac{i}{f(i)}=\frac{j}{f(j)}\) と同値です。

よって、各整数 \(i(1\le i \le N)\) に対して \(f(i)\) を求め、\(\frac{i}{f(i)}\) を全て求めればよいです。

\(f(i)\) はあらかじめ \(1\) 以上 \(N\) 以下の整数に対して平方数かどうか判定すれば \(i\) の約数を全探索することによって求められます。

計算量は \(\mathrm{O}(N\log N)\) です。

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<bool> sq(n+1,false);
  for(int i=1;i*i<=n;i++) sq[i*i]=true;
  vector<vector<int>> d(n+1);
  for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j+=i) d[j].push_back(i);
  }
  vector<int> cnt(n+1);
  for(int i=1;i<=n;i++){
    int f=0;
    for(int j=0;j<d[i].size();j++) if(sq[d[i][j]]) f=d[i][j];
    cnt[i/f]++;
  }
  int ans=0;
  for(int i=1;i<=n;i++) ans+=cnt[i]*cnt[i];
  cout<<ans<<endl;
}