Subtask 1: ~N \le 100, Q \le 10~.

Với subtask này, ta có thể duyệt mọi bộ ba ~A~, ~B~, ~C~, và tính được kết quả.

Độ phức tạp: ~O~ (~N^3 \times Q~).

Subtask 2: ~N \le 10^3, Q \le 10~.

Xuyên suốt bài toán, định nghĩa sau sẽ được sử dụng:

Gọi dạng square-free của một số là dạng mà đã bỏ đi tất cả các thừa số có số mũ chẵn.

Ví dụ:

~343 = 7^3~ ta sẽ rút gọn còn ~7~.

~20 = 2^2 \times 5~ ta sẽ rút gọn còn ~5~.

~9 = 3^2~ ta sẽ rút gọn còn ~1~.

~1029 = 7^3 \times 3~ ta sẽ rút gọn còn ~7 \times 3 = 21~.

Nhận xét: Hai số có tích là số chính phương khi và chỉ khi chúng có cùng dạng square-free.

Điều này có thể dễ dàng chứng minh bằng phản chứng. Nếu hai số không cùng dạng square-free, có nghĩa là tồn tại một thừa số có số mũ chẵn ở số này, nhưng có số mũ lẻ ở số kia. Khi nhân lại, thừa số đó sẽ có số mũ lẻ, từ đó, tích hai số không thể là số chính phương.

Ban đầu đặt ~a_i = i~ với ~1 \le i \le n~. Từ đây, ta sẽ rút gọn ~i~ thành dạng square-free. Ở subtask này, chúng ta có thể phân tích ra thừa số nguyên tố bằng thuật toán ~O~ (~\sqrt n~).

Bài toán trở thành tìm số bộ ba ~i, j, k~ mà ~a_i = a_j = a_k~. Điều này có thể thực hiện bằng mảng đếm và tổ hợp chập ~3~.

Độ phức tạp: ~O~ (~Q \times N \times \sqrt N~).

Subtask 3: ~N \le 5 \times 10^5~.

Vì ~Q~ lớn, ta sẽ nghĩ đến việc tiền xử lý các truy vấn.

Gọi ~res_i~ là kết quả khi ~N = i~.

Có thể thấy, khi chuyển từ ~i - 1~ lên ~i~, thì ta sẽ tăng ~cnt_{a_i}~ lên một, và cập nhật lại tổ hợp.

Đồng thời, ta có thể sử dụng sàng nguyên tố để phân tích thừa số nguyên tố.

Độ phức tạp: ~O~ (~N \times log~ ~n~ ~+~ ~Q~).

Subtask 4: ~N \le 10^7~.

Ta cần cải tiến bước phân tích thành thừa số nguyên tố.

Gọi ~p_i~ là ước nhỏ nhất của ~i~. Điều này có thể thực hiện trong ~O~ (~N \times~ ~log~ ~log~ ~N~).

Gọi ~square_i~ là dạng square-free của ~i~. Có ~square_1 = 1~ và ~square_2 = 2~.

Để tính ~square_i~, gọi ~x~ là một ước nguyên tố bất kỳ của ~i~. Tuy nhiên, để đơn giản, ta có thể lấy ~x = p_i~. Có thể chứng minh ~x~ sẽ là một số nguyên tố.

Lúc này, nếu ~square_{\frac {i}{x}}~ chia hết cho ~x~, điều đó có nghĩa, ~square_{\frac {i}{x}}~ đã có thừa số ~x~. Vì vậy, ~square_{i}~ ~=~ ~square_{\frac {i}{x}} / x~.

Ngược lại, ~square_i~ ~=~ ~square_{i}~ ~=~ ~square_{\frac {i}{x}} \times x~, vì ta sẽ phải thêm một thừa số ~x~.

Từ đó, ta dễ dàng tính được ~res_i~.

Độ phức tạp: ~O~ (~N \times~ ~log~ ~log~ ~N~ ~+~ ~Q~).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e7 + 9;

int n, a[N];
int p[N];
int d[N];
int res[N];
int cnt[N];

int c3 (int x){
    return x * (x - 1) * (x - 2) / 6;
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    if (fopen ("input.txt", "r")){
        freopen ("input.txt", "r", stdin);
        freopen ("output.txt", "w", stdout);
    }
    for (int i = 1; i < N; i++) p[i] = i;
    for (int i = 2; i * i < N; i++) if (p[i] == i){
        for (int j = i * i; j < N; j += i) p[j] = min (p[j], i);
    }
    d[1] = 1;
    for (int i = 2; i < N; i++){
        if (d[i / p[i]] % p[i] == 0) d[i] = d[i / p[i]] / p[i];
        else d[i] = d[i / p[i]] * p[i];
    }
    for (int i = 1; i < N; i++){
        res[i] = res[i - 1];
        res[i] -= c3 (cnt[d[i]]);
        cnt[d[i]]++;
        res[i] += c3 (cnt[d[i]]);
    }
    int q = 1; cin >> q;
    int finalres = 0;
    while (q--){
        int x; cin >> x; finalres ^= res[x];
    }
    cout << finalres;
}