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: