Problem Statement

You are given an integer $N$. Find the number of pairs $(i,j)$ of positive integers at most $N$ that satisfy the following condition:
$i×j$ is a square number.

Constraints

$1≤N≤2×10^5$

$N$ is an integer.

$令f(x)，为整数x中的因数中，最大的平方数$
$一个正整数n，如果n是平方数，则它的质因素分解n=\prod p_i^{e_i}，e_i均为偶数$
$x=\prod p_i^{e_i}，则f(x)=\prod q_i^{e’_i}，q_i为各个p_i中，e_i\geqslant 2的项，若e_i为偶数，e’_i=e_i，否则e’_i=e_i-1$
$故\dfrac{x}{f(x)}=\prod w_i，其中w_i为(p_1,p_2,…\)中为e_i为奇数的项$

$对于整数(i，j)，当且仅当\dfrac{i\times j}{f(i)\times f(j)}是一个平方数时，i\times j是平方数$

$证明：$
$充分性：$
$若\dfrac{i\times j}{f(i)\times f(j)}为平方数，其质因数分解\prod p_i^{e_i}中，e_i均为偶数，f(i)、f(j)的质因数分别是i、j质因数的子集，$
$且指数亦为偶数，i\times j=\dfrac{i\times j}{f(i)\times f(j)}\cdot f(i)\times f(j)的质因数分解中指数e_i均为偶数，i\times j为平方数$
$必要性：$
$i\times j为平方数，质因数分解的指数均为偶数，同理f(i)、f(j)的质因数分解是i、j质因数的子集且为偶数，$
$并且同一质因数对应的指数不大于i、j的质因数对应的指数，故\dfrac{i\times j}{f(i)\times f(j)}的质因数分解中e_i均为偶数$
$\dfrac{i\times j}{f(i)\times f(j)}是平方数$

$因为\dfrac{i}{f(i)}不能除以某个指数p两次或两次以上，\dfrac{i\times j}{f(i)\times f(j)}为平方数，当且仅当\dfrac{i}{f(i)}=\dfrac{j}{f(j)}$

$证明：$
$充分性：$
$\dfrac{i}{f(i)}=\dfrac{j}{f(j)}，\dfrac{i\times j}{f(i)\times f(j)}显然为平方数$
$必要性：$
$\dfrac{i}{f(i)}可以表示为\prod w_i，其中w_i的次数均为1，而一个平方数的质因数分解中的每个因数的次方都为偶数，$
$故\dfrac{j}{f(j)}的质因数分解中，至少需要出现\prod w_i^{e_i}，其中e_i为奇数且只能为1$
$此时\dfrac{j}{f(j)}再增加任何一个因数，\dfrac{i\times j}{f(i)\times f(j)}都不会是平方数，故\dfrac{i}{f(i)}=\dfrac{j}{f(j)}$

$有了以上的内容后，只要找出每个\dfrac{i}{f(i)}对应多少个数cnt，则有cnt\times cnt对数可以组成平方数$
$\dfrac{i\times j}{f(i)\times f(j)}$

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

const int N = 2e5 + 10, INF = 1e8;
const int mod = 998244353;

int n;
bool sq[N];
int cnt[N];
vector<int> d[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i * i <= n; i ++ ) sq[i * i] = true;
    //求所有小于等于n的数全部的因数
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j += i) d[j].push_back(i);

    for (int i = 1; i <= n; i ++ )
    {
        int f = 0;
        //找到i的因数中最大的平方数
        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];
    printf("%d\n", ans);
    return 0;
}