Hiểu bài toán

Bài toán yêu cầu tìm giá trị cuối cùng của một số nguyên lớn n (với n < 10^1000000) sau khi thực hiện lặp đi lặp lại thao tác thay thế số đó bằng tổng các chữ số của nó cho đến khi thu được một số có một chữ số. Ví dụ, với n = 101, tổng các chữ số là 2 (một chữ số), nên kết quả là 2.

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

Cách Mô phỏng trực tiếp bằng số

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    if (!(cin >> s)) return 0;

    // Xử lý trường hợp n là "0"
    if (s == "0") {
        cout << 0;
        return 0;
    }

    // Tính tổng các chữ số lần đầu tiên từ chuỗi string
    long long sum = 0;
    for (char c : s) {
        sum += (c - '0');
    }

    // Lặp lại việc tính tổng các chữ số cho đến khi sum < 10
    while (sum >= 10) {
        long long next_sum = 0;
        while (sum > 0) {
            next_sum += sum % 10;
            sum /= 10;
        }
        sum = next_sum;
    }

    cout << sum;

    return 0;
}

• Time Complexity: O(L + log(S))
• Space Complexity: O(1)

Phương pháp này thực hiện mô phỏng chính xác quy trình của bài toán. Bước đầu tiên, nó đọc chuỗi số rất dài và tính tổng các chữ số của nó. Vì n có thể có tới 1 triệu chữ số, tổng này có thể rất lớn (lên tới 9 triệu), nhưng vẫn nằm trong giới hạn của kiểu dữ liệu long long. Sau đó, nó sử dụng một vòng lặp while để tiếp tục chia nhỏ tổng đó cho đến khi nó trở thành một số có một chữ số.

• Bước 1: Duyệt qua chuỗi n để tính tổng các chữ số. Độ phức tạp là O(L) với L là độ dài chuỗi.
• Bước 2: Trong vòng lặp while, lấy tổng của các chữ số của số hiện tại. Vì số này nhỏ hơn 10 triệu, số lần lặp là rất ít (nhỏ hơn 7 lần).

Phương pháp này dễ hiểu và đúng đắn cho các số đầu vào lớn, nhưng phụ thuộc vào giả định rằng tổng ban đầu có thể lưu trong long long.

Cách Tối ưu hóa bằng toán học (Digital Root)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define en "\n"
#define Max 1000009
#define aq "aq"
const long long M = 1e9 + 7;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen(aq".inp","r")){
        freopen(aq".inp","r",stdin);
        freopen(aq".out","w",stdout);
    }
    string n;
    cin>>n;
    ll ans=0;
    for(char x:n){
        ans=(ans+(x-'0'))%9;
    }
    if(ans==0){
        cout<<9;
    }else{
        cout<<ans;
    }
}

• Time Complexity: O(L)
• Space Complexity: O(1) (không kể bộ nhớ lưu input)

Đây là phương pháp tối ưu nhất, dựa trên định lý về 'Gốc Kỹ thuật số' (Digital Root).

Định lý: Gốc kỹ thuật số của một số nguyên dương n (tức là kết quả cuối cùng của bài toán) bằng n mod 9. Nếu phép chia hết cho 9 thì kết quả là 9 (trừ trường hợp n = 0 thì kết quả là 0).

Thực hiện:

1. Đọc chuỗi n.
2. Tính tổng các chữ số của n modulo 9. Vì (a + b) mod 9 = ((a mod 9) + (b mod 9)) mod 9, ta có thể cộng dồn từng chữ số và lấy dư 9 ngay trong vòng lặp.
3. Nếu kết quả là 0, in ra 9. Ngược lại, in ra kết quả.

Phương pháp này bỏ qua hoàn toàn bước mô phỏng thứ hai, chỉ cần duyệt qua chuỗi đầu vào một lần duy nhất.

Cách Mô phỏng bằng chuỗi (Nếu số quá lớn)

#include<bits/stdc++.h>
using namespace std;
int main (){
string s;
cin >> s;
long long a = 0;
for(char x : s){
a += x - '0';
} 
while(a > 9){
long long s = 0;
do{
s += a % 10;
a/=10;
} while(a != 0);
a = s;
}
cout<<a;
}

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

Đây là một biến thể của Approach 1, nhưng được dùng khi số đầu vào quá lớn đến mức tổng các chữ số của nó cũng không thể lưu trữ trong các kiểu số nguyên cơ bản (ví dụ: n có 10^9 chữ số, tổng là 9 * 10^9, quá lớn cho long long - tuy nhiên với n < 10^1000000, long long vẫn đủ).

Nếu gặp một bài toán với giới hạn lớn hơn, ta sẽ phải:

1. Tính tổng các chữ số từ chuỗi đầu vào và lưu thành một chuỗi mới (hoặc một số lớn tùy chỉnh).
2. Nếu chuỗi mới có độ dài lớn hơn 1, thực hiện tính tổng các chữ số của nó.
3. Lặp lại cho đến khi chuỗi có độ dài 1.

Trong ngữ cảnh của bài toán này với n < 10^1000000, Approach 1 là đủ, nhưng Approach 2 (Toán học) là tốt nhất.

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

Bài học kinh nghiệm

• Bài toán này thực chất là tìm 'Gốc Kỹ thuật số' (Digital Root) của số n.
• Công thức tính Digital Root là n mod 9 (nếu n mod 9 == 0 và n > 0 thì kết quả là 9).
• Vì n rất lớn (đến 1 triệu chữ số), ta không thể lưu n vào kiểu số nguyên. Ta phải xử lý chuỗi.
• Để tính n mod 9, ta chỉ cần cộng tất cả các chữ số của n lại rồi lấy dư 9.

Lỗi thường gặp

• Xử lý sai trường hợp n = 0: Nếu n = 0, tổng các chữ số là 0, kết quả phải là 0. Tuy nhiên, với công thức n mod 9 thì 0 mod 9 = 0. Trong khi đó, quy tắc Digital Root thường được viết là: nếu số chia hết cho 9 thì trả về 9. Để tránh lỗi, cần kiểm tra riêng trường hợp input là '0'.
• Sử dụng sai kiểu dữ liệu: Cố gắng lưu n vào long long hoặc int sẽ gây tràn số (overflow) ngay lập tức vì n có thể có 1 triệu chữ số.
• Mô phỏng quá nhiều lần: Nếu dùng cách mô phỏng (Approach 1), phải đảm bảo vòng lặp dừng đúng (khi số < 10).