Tóm tắt đề bài

Một số được gọi là số đặc biệt nếu nó chia hết cho tổng các chữ số của chính nó.
Cho dãy \(A\) gồm \(n\) số nguyên dương. Có \(q\) truy vấn, mỗi truy vấn cho đoạn \([l,r]\), hãy đếm xem trong đoạn đó có bao nhiêu phần tử là số đặc biệt.

Phân tích

• Ràng buộc lớn: \(n, q \le 10^5\), nên không thể trả lời mỗi truy vấn bằng cách duyệt từng phần tử trong đoạn (sẽ là \(O(nq)\)).
• Mỗi \(a_i \le 10^9\) nên số chữ số tối đa là \(10\).
  • Việc tính tổng chữ số của một số là \(O(\text{số chữ số}) \le O(10)\), rất nhỏ.
• Bài toán quy về:
  1. Tiền xử lý mảng nhị phân \(b_i\) với \(b_i = 1\) nếu \(a_i\) là số đặc biệt, ngược lại \(0\).
  2. Trả lời truy vấn đếm số lượng \(1\) trong đoạn bằng mảng cộng dồn (prefix sum).

Hướng giải quyết

Nhận xét

Với mỗi vị trí \(i\), ta chỉ cần biết \(a_i\) có “đặc biệt” hay không. Khi đã có mảng \(b\), mọi truy vấn đếm trên đoạn trở thành bài toán chuẩn: đếm tổng đoạn, giải bằng prefix sum trong \(O(1)\) mỗi truy vấn.

Thuật toán

1. Đọc \(n, q\) và dãy \(a_1..a_n\).
2. Với từng \(a_i\):
   • Tính \(s = \text{sumDigits}(a_i)\).
   • Nếu \(a_i \bmod s = 0\) thì \(b_i = 1\), ngược lại \(b_i = 0\).

3. Tạo mảng cộng dồn \(pref\):

   \[pref[0] = 0,\quad pref[i] = pref[i-1] + b_i\]

4. Với mỗi truy vấn \((l,r)\), trả lời:

   \[\text{ans} = pref[r] - pref[l-1]\]

5. In kết quả cho từng truy vấn.

Lưu ý / Sai lầm hay gặp

• Tổng chữ số \(s\) luôn \(\ge 1\) vì \(a_i\) là số nguyên dương, nên không có trường hợp chia cho \(0\).
• Dùng kiểu long long cho an toàn (dù \(a_i \le 10^9\) vẫn vừa int).
• Nhớ mảng prefix có chỉ số từ \(0\) để tính đoạn \([l,r]\) thuận tiện.

Độ phức tạp

• Tiền xử lý:
  • Tính tổng chữ số cho \(n\) phần tử: \(O(n \cdot 10) \approx O(n)\)
• Mỗi truy vấn: \(O(1)\)
• Tổng:
  • Thời gian: \(O(n + q)\)
  • Bộ nhớ: \(O(n)\) cho mảng prefix

Code tham khảo

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

static int sumDigits(long long x) {
    int s = 0;
    while (x > 0) {
        s += (int)(x % 10);
        x /= 10;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int s = sumDigits(a[i]);
        int isSpecial = (a[i] % s == 0) ? 1 : 0;
        pref[i] = pref[i - 1] + isSpecial;
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << "\n";
    }
    return 0;
}