Hiểu bài toán

Một số nguyên dương N được gọi là 'số đẹp' nếu nó thỏa mãn một trong hai điều kiện: (1) N bằng 9, hoặc (2) Tổng các chữ số của N (gọi là f(N)) cũng là một số đẹp. Về bản chất, đây là một định nghĩa đệ quy. Khi ta tính tổng các chữ số của N, kết quả là một số nhỏ hơn N rất nhiều. Nếu ta lặp lại việc lấy tổng các chữ số cho đến khi chỉ còn một chữ số (số này được gọi là digital root), ta sẽ nhận thấy rằng N là số đẹp khi và chỉ khi digital root của N bằng 9. Ví dụ: 18 -> 1+8=9 (đẹp). 99 -> 9+9=18 -> 1+8=9 (đẹp). 10 -> 1+0=1 (không đẹp). Do đó, bài toán quy về việc kiểm tra xem tổng các chữ số của N có chia hết cho 9 hay không (tương đương digital root = 9, trừ trường hợp N=0 nhưng N là số nguyên dương).

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

Cách Tính tổng trực tiếp và kiểm tra

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        string n;
        cin >> n;
        long long sum = 0;
        for (char c : n) {
            sum += c - '0';
        }
        if (sum % 9 == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

• Time Complexity: O(L) với L là độ dài xâu N (tối đa ~100)
• Space Complexity: O(L)

Cách tiếp cận này dựa trên giả định (đúng trong bài toán này) rằng N là số đẹp nếu và chỉ khi tổng các chữ số của N chia hết cho 9. Ta đọc N dưới dạng xâu do N quá lớn (lên tới 10^100), duyệt qua từng ký tự, chuyển sang số và cộng dồn vào biến tổng. Sau đó chỉ cần kiểm tra điều kiện tổng chia hết cho 9. Các solution 1, 2, 3 đều sử dụng logic này.

Cách Tối ưu tính chia hết cho 9 (Digital Root)

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        string n;
        cin >> n;
        int sum_mod = 0;
        for (char c : n) {
            sum_mod = (sum_mod + (c - '0')) % 9;
        }
        if (sum_mod == 0) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

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

Đây là biến thể của cách tiếp cận 1, tối ưu hơn về mặt tính toán. Thay vì累加 (tích lũy) vào một biến số lớn (long long), ta chỉ cần lưu giá trị modulo 9 của tổng các chữ số. Một số chia hết cho 9 khi và chỉ khi tổng các chữ số của nó chia hết cho 9. Do đó, nếu t tổng các chữ số ban đầu chia hết cho 9, digital root của nó sẽ là 9, và N là số đẹp.

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

Bài học kinh nghiệm

• Bài toán có thể được suy diễn lại ngắn gọn: N là số đẹp nếu và chỉ khi tổng các chữ số của N chia hết cho 9.
• Do N có thể rất lớn (đến 10^100), bắt buộc phải xử lý N dưới dạng xâu (string) hoặc mảng ký tự.
• Tính chất digital root: Một số tự nhiên chia hết cho 9 khi và chỉ khi tổng các chữ số của nó chia hết cho 9.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu số nguyên (int, long long) để lưu N trực tiếp会导致 overflow (tràn số) do N quá lớn.
• Quên trường hợp N = 9 (theo điều kiện 1) dù tổng chữ số của 9 là 9 nên vẫn được bao phủ bởi điều kiện chia hết cho 9, nhưng cần cẩn thận với các định nghĩa đệ quy nếu có thay đổi.
• Xử lý sai việc chuyển ký tự thành số (ví dụ: dùng 'c' thay vì c - '0').