Bài A: Tối ưu giá trị cuối cùng sau dãy phép toán

Cho một mảng gồm n số nguyên phân biệt. Ta được thực hiện hai loại thao tác:

• Phép trừ: chọn hai phần tử x, y và thay bằng x - y.
• Phép lấy dư: chọn hai phần tử x, y và thay bằng x % y.

Mục tiêu là thu được giá trị lớn nhất có thể sau khi thực hiện đúng n-1 thao tác.

Nhận xét:

• Với phép trừ: để kết quả lớn nhất, ta nên giữ lại giá trị nhỏ nhất mn và dùng nó để trừ tất cả các giá trị khác. Kết quả cuối cùng sẽ là tổng - 2 * mn.
• Với phép lấy dư: vì mọi số đều khác nhau, tồn tại duy nhất một giá trị nhỏ nhất mn. Khi lấy bất kỳ số nào chia cho mn, kết quả luôn nhỏ hơn mn, do đó mn không bị thay đổi. Cuối cùng, giá trị còn lại chính là mn.

Do đó, đáp án cho cả hai trường hợp đều chỉ phụ thuộc vào tổng mảng và giá trị nhỏ nhất. Đặc biệt lưu ý trường hợp n = 1: lúc này không thực hiện thao tác nào, kết quả chính là phần tử duy nhất.

Bài B: Biến đổi xâu thành xâu đối xứng trong tối đa 2 thao tác

Cho xâu s độ dài n. Trong mỗi thao tác, có thể đổi một ký tự bất kỳ thành 'a'. Yêu cầu biến s thành xâu đối xứng với ít thao tác nhất (tối đa 2), đồng thời đảm bảo xâu kết quả có thứ tự từ điển nhỏ nhất.

Phân tích:

• Đầu tiên, xác định các vị trí i sao cho s[i] != s[n-i+1]. Gọi các cặp này là (d₁, n-d₁+1) và (d₂, n-d₂+1). Đề bài đảm bảo số cặp khác nhau ≤ 2.
• Trường hợp 0 cặp: xâu đã đối xứng. Dùng 2 thao tác để đổi các ký tự đầu tiên (không phải 'a') thành 'a', ưu tiên từ trái sang phải để tối ưu thứ tự từ điển.
• Trường hợp 1 cặp:
  • Nếu một trong hai ký tự đã là 'a', chỉ tốn 1 thao tác. Nếu n lẻ, có thể dùng thao tác còn lại để đổi ký tự giữa thành 'a'.
  • Nếu cả hai đều khác 'a', đổi cả hai thành 'a' (tốn đủ 2 thao tác).
• Trường hợp 2 cặp: Với mỗi cặp, đổi ký tự có thứ tự từ điển lớn hơn thành ký tự nhỏ hơn (ưu tiên 'a' nếu có). Không cần dùng hết 2 thao tác nếu đã đạt được xâu đối xứng tối ưu.

Bài C: Đếm cạnh có tổng trọng số là số nguyên tố

Cho cây có n đỉnh, mỗi đỉnh có trọng số. Đếm số cạnh mà tổng trọng số của hai đầu mút là số nguyên tố.

Giải pháp:

• Không cần DFS hay duyệt cây phức tạp. Chỉ cần duyệt từng cạnh (được cung cấp trong input), tính tổng trọng số hai đỉnh kề.
• Sử dụng sàng Eratosthenes để đánh dấu các số nguyên tố đến giới hạn 2 × 10⁶ (vì trọng số ≤ 10⁶).
• Với mỗi cạnh, kiểm tra tổng có phải nguyên tố không; nếu có thì tăng biến đếm.

Bài D: Tối đa hóa số lượng phần tử bằng nhau trong mảng kết quả

Cho mảng a độ dài n. Xây dựng mảng c sao cho c_i = floor(a_i / b_i), với b_i ≥ 1. Mục tiêu là chọn b để số lượng phần tử bằng nhau trong c là lớn nhất.

Ý tưởng:

• Với mỗi giá trị x (kết quả có thể của c_i), đếm xem có bao nhiêu chỉ số i sao cho tồn tại b_i thỏa floor(a_i / b_i) = x.
• Điều kiện tương đương: x ≤ a_i / b_i < x+1 → b_i ∈ [ceil(a_i/(x+1)), floor(a_i/x)]. Tuy nhiên cách này khó triển khai.
• Cách hiệu quả hơn: đổi hướng duyệt. Với mỗi giá trị i (coi như b_i = i), xét các bội j = i, 2i, 3i, ... ≤ 5×10⁶. Khi đó, với mọi a_k ∈ [j, j+i-1], ta có floor(a_k / i) = j/i = x.
• Sử dụng mảng đếm tần suất freq cho a, rồi xây dựng mảng tiền tố pref để truy vấn nhanh số phần tử trong đoạn [L, R].
• Để tránh đếm trùng khi nhiều i sinh ra cùng x, với mỗi x, chỉ cộng thêm phần đoạn mới chưa được xử lý trước đó.

Đoạn mã minh họa (đã điều chỉnh logic và tên biến):

int n = read();
vector<int> freq(MAX_A + 1, 0);
for (int i = 0; i < n; ++i) {
    int val = read();
    if (val <= MAX_A) freq[val]++;
}
vector<long long> pref(MAX_A + 1, 0);
for (int i = 1; i <= MAX_A; ++i) {
    pref[i] = pref[i-1] + freq[i];
}

long long ans = 0;
// Đếm các phần tử a_i < 10^6 → c_i = 0 khi chọn b_i đủ lớn
for (int i = 0; i < n; ++i) {
    if (a[i] < 1000000) ans++;
}

const int MAX_X = 5000000;
vector<pair<int, int>> last_interval(MAX_X + 1, {-1, -1});
vector<long long> count_x(MAX_X + 1, 0);

for (int b = 1; b <= 1000000; ++b) {
    for (int j = b, x = 1; j <= MAX_X; j += b, ++x) {
        int L_new = j;
        int R_new = min(j + b - 1, MAX_X);
        auto [L_old, R_old] = last_interval[x];
        long long add = 0;
        if (R_old < L_new) {
            add = pref[R_new] - pref[L_new - 1];
        } else if (R_old < R_new) {
            add = pref[R_new] - pref[R_old];
        }
        count_x[x] += add;
        last_interval[x] = {L_new, R_new};
        ans = max(ans, count_x[x]);
    }
}
cout << ans << '\n';

Lưu ý: Có trường hợp đặc biệt khi nhiều giá trị a_i lớn (gần 5×10⁶) có thể cùng tạo ra cùng một giá trị x nhỏ (ví dụ x=7) nhờ chọn b_i phù hợp. Bộ test dưới đây kiểm tra khả năng xử lý trường hợp này:

Input:
10
7 14 28 4000001 4000002 4000003 4000004 4000005 4000006 4000007

Output:
10