Gốc số (Digital Root) của số nguyên lớn trong C++

Giới thiệu

Gốc số (Digital Root) của một số là kết quả lặp lại cộng các chữ số cho đến khi còn 1 chữ số.

Ví dụ

n = 12345

1 + 2 + 3 + 4 + 5 = 15
1 + 5 = 6
Digital Root = 6

Công thức toán học

Digital Root có công thức trực tiếp:

• Nếu n = 0: DR = 0
• Nếu n % 9 == 0: DR = 9
• Ngược lại: DR = n % 9

Điều này đúng vì 10 ≡ 1 (mod 9), nên số bất kỳ ≡ tổng chữ số (mod 9).

Mã nguồn hoàn chỉnh

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

int digitalRoot(string n) {
    int digitsSum = 0;
    for (int i = 0; i < n.length(); i++) {
        digitsSum += n[i] - '0';
    }
    
    if (digitsSum == 0) return 0;
    return (digitsSum % 9 == 0) ? 9 : digitsSum % 9;
}

int main() {
    string n = "12345";
    cout << "Digital Root: " << digitalRoot(n) << endl;
    return 0;
}

Kết quả chạy chương trình

Digital Root: 6

Bảng tra nhanh Digital Root

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

• Thời gian: O(len) - len là độ dài chuỗi
• Không gian: O(1)

Ứng dụng thực tế

• Kiểm tra số học (casting out nines) - kiểm tra phép tính nhanh
• Thuật toán băm (hashing)
• Sinh số may mắn, numerology
• Nén dữ liệu, checksum

Mở rộng: Tính Digital Root cho số trong cơ số khác

int digitalRootBase(string n, int base) {
    int sum = 0;
    for (char c : n) {
        int digit = (c >= '0' && c <= '9') ? c - '0' : c - 'A' + 10;
        sum += digit;
    }
    if (sum == 0) return 0;
    int mod = base - 1;
    return (sum % mod == 0) ? mod : sum % mod;
}

Kết luận

Digital Root là khái niệm thú vị trong lý thuyết số, có công thức O(1) sau khi tính tổng chữ số, thay vì lặp lại nhiều lần.