Hiểu bài toán

Bài toán yêu cầu tính tổng các chữ số của một số nguyên dương n cho nhiều test case. Tuy nhiên, có một điểm đặc biệt: các giải pháp accepted cho thấy bài toán này thực chất là tìm 'digital root' (gốc số học) của n. Digital root của một số là giá trị thu được bằng cách cộng liên tục các chữ số của nó cho đến khi chỉ còn một chữ số. Ví dụ, digital root của 38 là 2 (3 + 8 = 11, 1 + 1 = 2). Các giải pháp cho thấy đầu vào có thể là một số lớn và cần xử lý nhiều test case.

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

Cách Brute Force - Lặp đệ quy

#include <bits/stdc++.h>
using namespace std;
int whl(int n) {
    int s = 0;
    while (n != 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}
int main() {
    freopen("digits.inp", "r", stdin);
    freopen("digits.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q; cin >> q;
    while (q--) {
        int n; cin >> n;
        cout << whl(whl(whl(n))) << endl;
    }
    return 0;
}

• Time Complexity: O(log^2 n) ~ O(log n)
• Space Complexity: O(1)

Phương pháp này sử dụng hàm whl để tính tổng các chữ số của một số. Vì whl(n) giảm rất nhanh (ví dụ, số có 10 chữ số lớn nhất là 9,999,999,999, tổng chữ số là 90), việc gọi hàm whl ba lần liên tục đảm bảo kết quả là một số có một chữ số. Đây là cách tiếp cận mô phỏng trực tiếp quá trình tính digital root. Độ phức tạp phụ thuộc vào số lần lặp, nhưng vì số lần lặp là hằng số (hoặc rất nhỏ), nó rất hiệu quả.

Cách Toán học - Công thức Digital Root

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("Digits.inp","r",stdin);
    freopen("Digits.out","w",stdout);
    int t;
    cin >> t;
    while (t--)
    {
        long long n;
        cin >> n;

        if (n % 9 == 0)
            cout << 9 << '\n';
        else
            cout << n % 9 << '\n';
    }
    return 0;
}

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

Đây là phương pháp tối ưu nhất dựa trên tính chất toán học của digital root. Digital root của một số n (với n > 0) bằng n mod 9. Nếu n chia hết cho 9, digital root là 9. Công thức: dr(n) = 1 + (n - 1) % 9. Các giải pháp như của DatBell (x-1) % 9 + 1 và truongik if (n % 9 == 0) ... else ... đều dựa trên chính tính chất này. Phương pháp này bỏ qua hoàn toàn việc tính tổng các chữ số.

Cách Optimized Simulation - Mô phỏng tối ưu

#include <iostream>
using namespace std;
int main(){
    freopen("digits.inp","r",stdin);
    freopen("digits.out","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        cout<<(x-1) % 9 + 1<<'\n';
    }
}

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

Đây là cách viết gọn của phương pháp toán học. Nó sử dụng công thức (x-1) % 9 + 1 để tính digital root trực tiếp mà không cần phân nhánh if-else. Đây là cách hiệu quả nhất về mặt mã nguồn và tốc độ chạy.

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

Bài học kinh nghiệm

• Bài toán thực chất là tìm Digital Root của số n, không chỉ đơn giản là tính tổng một lần.
• Có một công thức toán học tốc độ cao để tính Digital Root: dr(n) = 1 + (n - 1) % 9 (với n > 0).
• Nếu chỉ mô phỏng việc cộng các chữ số, số lần lặp là rất ít (thường chỉ mất 2-3 bước để giảm số về một chữ số), nên độ phức tạp logarit cũng rất nhanh.

Lỗi thường gặp

• Lầm tưởng rằng chỉ cần cộng các chữ số một lần là đủ (ví dụ: 38 -> 11). Cần lặp cho đến khi kết quả chỉ còn một chữ số.
• Xử lý sai trường hợp n chia hết cho 9 (công thức n % 9 sẽ trả về 0 thay vì 9).
• Độ dài số đầu vào có thể lớn, cần sử dụng kiểu dữ liệu phù hợp (ví dụ: long long), mặc dù công thức toán học có thể xử lý số lớn nếu lấy modulo.