\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Cách tiếp cận khác}}\)

• Giải theo hướng toán học và cải tiến dần

\(\color{green}{\text{Nhận xét}}\)

• Phân tích dưới dạng thừa số nguyên tố để tìm quy luật

Khi phân tích các số \(a, b, c\) về dạng \(p_1 ^{f_1} \times p_2 ^{f_2} \times ... \times p_k ^{f_k}\) với \(p_i\) nguyên tố phân biệt, \(k_i\) số mũ nguyên dương

Số chính phương là số có dạng \(p_1 ^{f_1} \times p_2 ^{f_2} \times ... \times p_k ^{f_k}\) với \(p_i\) nguyên tố phân biệt, \(k_i\) số mũ chẵn nguyên dương

Vậy tích của một cặp \((x, y)\) bất kì là số chính phương \(\Leftrightarrow\) các số mũ \(f_1, f_2, ..., f_k\) của \(x\) và \(y\) đều phải cùng chẵn hoặc cùng lẻ vì khi đó tổng số mũ mỗi nguyên tố đều chẵn.

\(\color{orange}{\text{Xử lí}}\)

• Nếu phải duyệt qua từng bộ \(k\) số mũ thì độ phức tạp rất là cao, nên ta sẽ đưa nó về dạng chung để xử lí nhanh hơn

• Ta chỉ quan tâm chẵn lẻ của số mũ, nên không mất tính tổng quát, ta có thể lấy các số mũ modulo cho 2

Với \(x \equiv p \pmod{2} \Leftrightarrow x\) % \(2 = p\)

Giả sử có \(x = p_1 ^{f_1} \times p_2 ^{f_2} \times \dots \times p_k ^{f_k}\)

Gọi \(mask(x) = p_1 ^{f_1 \% 2} \times p_2 ^{f_2 \% 2} \times ... \times p_k ^{f_k \% 2}\)

Khi đó ta có \(mask(x)\) là số nguyên dương nhỏ nhất để \(mask(x) \times x\) là số chính phương

\(\color{goldenrod}{\text{Tính toán kết quả}}\)

• Duyệt \(a = 1 \rightarrow n\)

Gọi \(cnt(mask(a))\) là số lượng số \(j \leq i\) thỏa mãn \(mask(j) = mask(i)\). Khi ráp lại sẽ ra được số chính phương

Tại mỗi vị trí \(i\) có \(f(cnt) = \frac{cnt \cdot (cnt - 1)}{2}\) cách chọn 2 số \(b, c\) còn lại thỏa điều kiện đề bài

Sau khi tính toán nhớ tăng \(cnt(mask(a))\) thêm 1 lần

Khi đó kết quả sẽ là tổng của các \(f(cnt)\) tại mỗi giá trị \(a\)

\(\color{purple}{\text{Độ phức tạp}}\)

• Ta có thể sàng nguyên tố trong \(O(n)\)

• Phân tích thừa số nguyên tố trong \(O(log n)\)

• Đếm và cập nhật số lượng \(cnt(mask)\) trong \(O(1)\)

• Đếm được số cách ghép cặp \(f(x)\) trong \(O(1)\)

• Tính toán trong \(O(n\ log\ max(a))\)

• Tổng cộng là \(O(n\ log(max(a))\) thời gian và \(O(n)\) bộ nhớ

• Tuy nhiên nghe đồn cũng có cách để làm trong \(O(n)\) thời gian bằng cách sàng luôn cả việc tính toán đó bằng một cách ma thuật nào đó ¯\_(ツ)_/¯

\(\color{green}{\text{Reference AC Code }}\): Online Solving, Factorization, Sieving, Math, DP_count

\(^{^{\color{purple}{\text{Complexity : }} O(n \times log(max(a)))\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

vector<int> prime; /// prime list
vector<int> lpf;   /// Lowest prime factor, lpf[x] is smallest prime divisor of x
void sieve(int lim = LIM) /// O(n)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    lpf[1] = 1; /// For easier calculation but can cause inf loops
    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2) prime.push_back(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

/// mask(x) is smallest positive number that mask(x) * x is a perfect square
int getMask(int x) /// O(log n)
{
    int mask = 1;
    while (x > 1) {
        int p = lpf[x], f = 0;
        do x /= p, f++; while (p == lpf[x]);
        if (f & 1) mask *= p; /// if current power is odd, we mutiple mask with current prime
    }
    return mask;
}

/// nC2 = number of ways to choose another 2 numbers
ll f(int x) { return 1LL * x * (x - 1) / 2; }
ll magic(int n) /// O(n log max(a))
{
    vector<int> cnt(n + 1, 0); /// Save the frequency of each mask
    ll res = 0;
    for (int a = 1; a <= n; ++a) /// Check all cases of a
        res += f(cnt[getMask(a)]++);

    return res;
}

int main() /// O(n log max(a))
{
    int n;
    cin >> n;
    sieve(n + 500);
    cout << magic(n);    
    return 0;
}