Editorial for maxdiv: Đếm đoạn chia hết

Hiểu bài toán

Bài toán yêu cầu đếm số lượng cặp chỉ số (l, r) sao cho đoạn con từ l đến r (al, ..., ar) chứa tối đa 1 số chia hết cho k.

Về bản chất, ta cần chia các vị trí của mảng thành các khối:

1. Các đoạn không chứa số chia hết nào.
2. Các đoạn chứa đúng 1 số chia hết.

Giả sử ta chỉ định các vị trí chứa số chia hết là 'điểm'. Một đoạn (l, r) hợp lệ có thể:

• Nằm hoàn toàn giữa hai điểm liên tiếp (chứa 0 điểm).
• Bao gồm một điểm ở giữa, và kéo dài sang trái/phải nhưng không chạm điểm khác (chứa đúng 1 điểm).

Ví dụ: Mảng [1, 2, 3, 4, 5] với k=2. Các số chia hết nằm ở vị trí 2 và 4.

• Các đoạn không chứa số chia hết: nằm giữa các điểm (1, 2), (2, 4), (4, 5).
• Các đoạn chứa đúng 1 số chia hết: ví dụ đoạn có chứa vị trí 2, kéo dài từ đầu mảng hoặc từ số chia hết trước đó đến vị trí 4.

Các cách tiếp cận

Cách Brute Force

// Đơn giản là duyệt qua tất cả các cặp (l, r)
// Duyệt l từ 1 đến N, r từ l đến N
// Duyệt qua đoạn a[l...r] đếm số chia hết cho k
// Nếu count <= 1 thì tăng biến đếm.

int count = 0;
for (int l = 1; l <= N; l++) {
    int div_count = 0;
    for (int r = l; r <= N; r++) {
        if (a[r] % k == 0) div_count++;
        if (div_count <= 1) count++;
        else break; // Tối ưu: nếu đã quá 1 số chia hết thì đoạn dài hơn cũng không thỏa mãn
    }
}

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Cách tiếp cận trực quan nhất. Duyệt qua tất cả các đoạn con có thể và kiểm tra điều kiện. Với mỗi đoạn, ta đếm số lượng phần tử chia hết cho k.

• Nếu số lượng là 0 hoặc 1, ta cộng vào kết quả.
• Vì ta chỉ cần tối đa 1 số chia hết nên khi gặp số chia hết thứ 2, ta có thể dừng duyệt r để tối ưu.

Cách này chỉ khả thi với N nhỏ (≤ 2000). Với N = 300,000, nó sẽ bị TLE.

Cách Two Pointers (Sliding Window)

// Sử dụng kỹ thuật hai con trỏ (Sliding Window)
// Giữ một cửa sổ [left, right]
// Di chuyển right từ 1 đến N
// Khi số lượng số chia hết > 1, di chuyển left cho đến khi thỏa mãn điều kiện

long long ans = 0;
int left = 1;
int cnt = 0; // đếm số chia hết trong đoạn [left, right]

for (int right = 1; right <= N; right++) {
    if (a[right] % k == 0) cnt++;

    while (cnt > 1) {
        if (a[left] % k == 0) cnt--;
        left++;
    }

    // Đoạn [left, right], [left+1, right], ..., [right, right] đều hợp lệ
    ans += (right - left + 1);
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận tổng quát cho các bài toán đếm đoạn con thỏa mãn điều kiện về số lượng phần tử đặc biệt.

Luận lý:

• Ta duyệt右端点 (right) từ 1 đến N.
• Với mỗi right, ta cố gắng tìm左端点 (left) nhỏ nhất sao cho đoạn [left, right] có tối đa 1 số chia hết.
• Biến cnt lưu số lượng số chia hết trong đoạn hiện tại.
• Nếu cnt > 1, ta phải loại bỏ các phần tử ở đầu đoạn (tăng left) cho đến khi cnt <= 1.
• Lúc này, mọi đoạn con kết thúc tại right và bắt đầu từ left đến right đều hợp lệ. Số lượng đoạn là right - left + 1.

Vì left và right chỉ tăng lên (không bao giờ lùi lại), độ phức tạp là O(N).

Cách Combinatorics (Math)

// Gom nhóm các vị trí chia hết
// Gọi các vị trí chia hết là p1, p2, ..., pm
// Thêm p0 = 0, p_{m+1} = N + 1

// 1. Đếm các đoạn KHÔNG chứa số chia hết
// Nằm giữa các vị trí chia hết. Ví dụ giữa p1 và p2
// Khoảng cách là (p2 - p1 - 1)
// Số đoạn con trong khoảng này là x*(x+1)/2

// 2. Đếm các đoạn chứa CHÍNH XÁC 1 số chia hết
// Xét vị trí pi là số chia hết duy nhất trong đoạn.
// Đoạn có thể bắt đầu từ sau p_{i-1} (đến pi) và kết thúc trước p_{i+1} (từ pi)
// Số cách chọn start: (pi - p_{i-1})
// Số cách chọn end: (p_{i+1} - pi)
// Tổng: (pi - p_{i-1}) * (p_{i+1} - pi)

long long ans = 0;
vector<int> pos;
pos.push_back(0);
for (int i = 1; i <= N; i++) {
    if (a[i] % k == 0) pos.push_back(i);
}
pos.push_back(N + 1);

// Đếm đoạn không có số chia hết
for (int i = 0; i < (int)pos.size() - 1; i++) {
    long long len = pos[i+1] - pos[i] - 1;
    ans += len * (len + 1) / 2;
}

// Đếm đoạn có đúng 1 số chia hết
for (int i = 1; i < (int)pos.size() - 1; i++) {
    ans += (long long)(pos[i] - pos[i-1]) * (pos[i+1] - pos[i]);
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận tối ưu nhất, biến bài toán thành bài toán toán học.

Ta chỉ cần quan tâm đến các vị trí chứa số chia hết cho k. Gọi các vị trí này là p1, p2, ..., p_m.

1. Các đoạn không chứa số chia hết nào: Các đoạn này nằm hoàn toàn giữa các số chia hết liên tiếp. Khoảng giữa pi và p{i+1} có độ dài d = p_{i+1} - p_i - 1. Số đoạn con tạo thành từ d phần tử liên tiếp là d * (d + 1) / 2.

2. Các đoạn chứa đúng 1 số chia hết: Xét số chia hết tại pi. Để đoạn chỉ chứa pi:

   • Left side: Đoạn có thể bắt đầu từ bất kỳ đâu sau p{i-1} (để không chứa p{i-1}) và kết thúc tại p_i. Số cách: p_i - p_{i-1}.
   • Right side: Đoạn có thể kết thúc tại bất kỳ đâu trước p{i+1} (để không chứa p{i+1}) và bắt đầu tại p_i. Số cách: p_{i+1} - p_i.
   • Tổng kết hợp: (p_i - p_{i-1}) * (p_{i+1} - p_i).

Cách này chạy rất nhanh và không dùng phép chia lặp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề có thể được chia thành 2 trường hợp độc lập: đoạn chứa 0 số chia hết và đoạn chứa 1 số chia hết.
• Bài toán có thể quy về đếm số đoạn con giữa các vị trí đặc biệt (số chia hết) thay vì duyệt trực tiếp các giá trị.
• Sử dụng mảng đánh dấu hoặc mảng prefix giúp định vị các số chia hết nhanh chóng.

Lỗi thường gặp

• Sai lệch về số mũ (off-by-one) khi tính toán khoảng cách giữa các vị trí chia hết. Ví dụ: tính độ dài dải không chia hết là p_{i+1} - p_i thay vì p_{i+1} - p_i - 1.
• Tràn số nguyên (Integer Overflow) khi tính kết quả. Vì N có thể lên tới 300,000, số đoạn con có thể lên tới ~4.5 * 10^10, bắt buộc phải dùng long long (64-bit integer).
• Quên xử lý các đoạn nằm trước vị trí chia hết đầu tiên và sau vị trí chia hết cuối cùng.