Editorial for ptit053: Số mạnh mẽ

Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên dương trong khoảng từ (l, r] (tức là lớn hơn l và nhỏ hơn hoặc bằng r) mà có tổng các chữ số là một số nguyên tố. Ví dụ, với l=17 và r=20, ta xét các số 18, 19, 20. Tổng chữ số của 18 là 9 (không nguyên tố), 19 là 10 (không nguyên tố), 20 là 2 (nguyên tố). Do đó kết quả là 1.

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

Cách Brute Force

#include <stdio.h>
#include <math.h>

int nt(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return n > 1;
}

int chuso(int n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return nt(sum);
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int sum = 0;
    for (int i = a + 1; i <= b; i++) {
        if (chuso(i)) sum++;
    }
    printf("%d", sum);
    return 0;
}

• Time Complexity: O((r-l) * sqrt(M)), với M là tổng chữ số lớn nhất (với r <= 100000, M <= 36)
• Space Complexity: O(1)

Phương pháp này duyệt qua từng số trong khoảng (l, r]. Với mỗi số, nó tính tổng các chữ số bằng cách lặp và chia lấy dư, sau đó kiểm tra xem tổng đó có phải là số nguyên tố hay không bằng một vòng lặp kiểm tra ước số.

• Hàm nt(n): Kiểm tra số nguyên tố, trả về 1 nếu là số nguyên tố, 0 nếu không.
• Hàm chuso(n): Tính tổng chữ số của n và gọi nt() để kiểm tra.
• Vòng lặp main: Duyệt từ a+1 đến b, tăng biến đếm nếu chuso(i) trả về 1.

Độ phức tạp thời gian: O(r * sqrt(M)), nhưng với r tối đa là 100,000 và tổng chữ số tối đa là 36, số lần lặp trong hàm nt là rất nhỏ (tối đa sqrt(36) = 6), nên chạy rất nhanh.

Cách Prefix Sum

#include <stdio.h>
#include <math.h>

int nt(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return n > 1;
}

int tong(int n) {
    int ans = 0;
    while (n) {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}

int pre[100005];

int main() {
    int l, r;
    scanf("%d %d", &l, &r);
    pre[1] = 0;
    for (int i = 2; i <= 100004; i++) {
        pre[i] = pre[i-1] + (nt(tong(i)) ? 1 : 0);
    }
    printf("%d", pre[r] - pre[l]);
    return 0;
}

• Time Complexity: O(N + Q), với N = 100005 (giới hạn)
• Space Complexity: O(N)

Phương pháp này sử dụng kỹ thuật tiền tố (Prefix Sum) để tối ưu hóa việc truy vấn nhiều lần hoặc xử lý dãy số.

1. Chuẩn bị: Mảng pre được xây dựng trước, trong đó pre[i] lưu số lượng số mạnh mẽ từ 1 đến i.
2. Xây dựng: Duyệt từ 2 đến 100004, tính pre[i] = pre[i-1] + (1 nếu i là số mạnh mẽ, 0 nếu không).
3. Truy vấn: Số lượng số mạnh mẽ trong (l, r] bằng pre[r] - pre[l].

Độ phức tạp: Việc xây dựng mảng tốn O(N * sqrt(M)), nhưng chỉ cần làm một lần. Việc tra câu trả lời tốn O(1).

Cách Optimized Brute Force

#include <stdio.h>
#include <math.h>

long long int snt(long long int n) {
    if (n <= 1) return 0;
    for (long long int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

long long int somanhme(long long int n) {
    long long int sum = 0, x = n;
    while (x != 0) {
        sum += x % 10;
        x /= 10;
    }
    return snt(sum);
}

int main() {
    long long int a, b, dem = 0;
    scanf("%lld %lld", &a, &b);
    for (long long int i = a + 1; i <= b; i++) {
        if (somanhme(i)) dem++;
    }
    printf("%lld", dem);
    return 0;
}

• Time Complexity: O((r-l) * sqrt(M))
• Space Complexity: O(1)

Đây là biến thể của phương pháp Brute Force, tương tự như phương pháp 1 nhưng sử dụng kiểu dữ liệu long long int để đảm bảo an toàn số nguyên nếu giới hạn thay đổi, và đặt tên biến theo cách khác. Logic cơ bản vẫn là duyệt từng số và kiểm tra thủ công.

• Hàm snt: Kiểm tra số nguyên tố.
• Hàm somanhme: Tính tổng chữ số và kiểm tra.
• Vòng lặp main: Duyệt và đếm.

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

Bài học kinh nghiệm

• Tổng các chữ số của một số bất kỳ trong khoảng [1, 100000] nằm trong khoảng [1, 36] (vì 99999 có tổng là 45, nhưng 100000 có tổng là 1). Do đó, ta chỉ cần kiểm tra tính nguyên tố cho các số nhỏ (tối đa 45), nên việc kiểm tra nguyên tố có thể thực hiện rất nhanh.
• Vì dữ liệu đầu vào nhỏ (r <= 100000), các phương pháp brute force đều có thể chấp nhận được. Tuy nhiên, phương pháp Prefix Sum cho thời gian tra câu trả lời nhanh nhất O(1).

Lỗi thường gặp

• Đoạn khoảng (l, r]: Lỗi thường gặp là duyệt từ l đến r (bao gồm l) hoặc l+1 đến r-1. Đề bài yêu cầu (l, r], nghĩa là số lớn hơn l và nhỏ hơn hoặc bằng r. Do đó vòng lặp phải là for (i = l + 1; i <= r; i++).
• Kiểm tra số nguyên tố cho số 1: Hàm kiểm tra số nguyên tố cần trả về false (0) cho số 1.
• Kiểu dữ liệu: Trong một số trường hợp, nếu r lớn hơn 100000 một chút, việc dùng int cho mảng pre hoặc biến đếm có thể gây tràn số (nếu số lượng số mạnh mẽ lớn), nhưng với ràng buộc đề bài này thì int là đủ.