~\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;
}