Official

D - Together Square Editorial by en_translator


Let \(f(N)\) be the largest square divisor of an integer \(N\).

Then, for integers \(i\) and \(j\), \(i \times j\) is a square number if and only if \(\frac{i \times j}{f(i) \times f(j)}\) is a square number.

Since \(\frac{i}{f(i)}\) is indivisible by a prime \(p\) twice or more, \(\frac{i \times j}{f(i) \times f(j)}\) is a square number if and only if \(\frac{i}{f(i)}=\frac{j}{f(j)}\)

Therefore, it is sufficient to find \(f(i)\) for each integer \(i(1\le i \le N)\), and to find \(\frac{i}{f(i)}\).

After checking if each integer from \(1\) through \(N\) is a square number, we can find \(f(i)\) by bruteforcing every divisor of \(i\).

The complexity is \(\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;
}

posted:
last update: