Tóm tắt đề bài

Cho một số tự nhiên \(n\). Cần tính tổng tất cả các chữ số của các số từ \(1\) đến \(n\).

• Ví dụ: Với \(n = 12\), các số từ 1 đến 12 là: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.
• Tổng các chữ số: \(1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2) = 51\).

Phân tích

• Giới hạn: \(n \le 10^{12}\).
• Với \(n\) lên đến \(10^{12}\), ta không thể duyệt qua từng số từ \(1\) đến \(n\) để tính tổng chữ số vì độ phức tạp sẽ là \(O(n \cdot \log n)\), vượt quá giới hạn thời gian cho phép.
• Bài toán này yêu cầu một cách tiếp cận tối ưu hơn, cụ thể là tính toán số lần xuất hiện của mỗi chữ số ở từng hàng (đơn vị, chục, trăm,...) hoặc sử dụng phương pháp đếm theo vị trí chữ số.
• Độ phức tạp mục tiêu: \(O(\log_{10} n)\), tương ứng với số lượng chữ số của \(n\).

Hướng giải quyết

Ý tưởng chính

Ta sẽ xét từng vị trí hàng của chữ số (hàng đơn vị, hàng chục, hàng trăm,...) và tính xem các chữ số từ \(0\) đến \(9\) đóng góp bao nhiêu vào tổng tại vị trí đó.

Giả sử ta đang xét hàng có giá trị là \(Pow\) (ví dụ \(Pow=100\) là hàng trăm). Số \(n\) được chia thành 3 phần:

1. L (Left): Phần số đứng trước hàng đang xét.
2. x: Chữ số tại hàng đang xét.
3. R (Right): Phần số đứng sau hàng đang xét.

Ví dụ: \(n = 12345\), xét hàng trăm (\(Pow = 100\)):

• \(L = 12\)
• \(x = 3\)
• \(R = 45\)

Công thức tính cho mỗi hàng

Tại mỗi hàng \(Pow\), tổng đóng góp vào kết quả được tính qua 3 thành phần:

1. Đóng góp từ các chu kỳ đầy đủ của \(L\):
   Mỗi chữ số từ \(0\) đến \(9\) xuất hiện \(L \times Pow\) lần. Tuy nhiên, chữ số \(0\) không đóng góp vào tổng giá trị chữ số. Tổng các chữ số từ \(1\) đến \(9\) là \(1+2+...+9 = 45\).
   

   \[ Res_1 = L \times Pow \times 45 \]

2. Đóng góp từ chữ số hiện tại \(x\):
   Chữ số \(x\) xuất hiện ở hàng này trong các số từ \(L \cdot 10 \cdot Pow + x \cdot Pow + 0\) đến \(L \cdot 10 \cdot Pow + x \cdot Pow + R\). Vậy có \((R + 1)\) số mà tại hàng này có chữ số \(x\).
   

   \[ Res_2 = x \times (R + 1) \]

3. Đóng góp từ các chữ số nhỏ hơn \(x\) (từ \(1\) đến \(x-1\)):
   Các chữ số \(i \in [1, x-1]\) xuất hiện trọn vẹn \(Pow\) lần tại hàng này (khi phần bên trái là \(L\)).
   Tổng đóng góp là: \((1 + 2 + ... + (x-1)) \times Pow\).
   Công thức tổng dãy số: \(1 + 2 + ... + (x-1) = \frac{x(x-1)}{2}\).
   

   \[ Res_3 = \frac{x(x-1)}{2} \times Pow \]

Cộng dồn cả 3 phần này cho tất cả các hàng từ hàng đơn vị đến hàng cao nhất của \(n\) ta sẽ được kết quả cuối cùng.

Độ phức tạp

• Thời gian: \(O(\log_{10} n)\), do ta lặp qua từng chữ số của \(n\). Với \(n = 10^{12}\), vòng lặp chỉ chạy khoảng 13 lần.
• Bộ nhớ: \(O(1)\), chỉ sử dụng một vài biến số nguyên.

Code tham khảo

import sys

def solve():
    # Đọc dữ liệu vào
    try:
        line = sys.stdin.readline()
        if not line:
            return
        n = int(line.strip())
    except EOFError:
        return

    res = 0
    pow_val = 1 # 1: Đơn vị; 10: Chục; 100: Trăm...

    while pow_val <= n:
        # Tách số n thành 3 phần tại vị trí pow_val
        # Ví dụ n = 12345, pow_val = 100
        r = n % pow_val            # Phần bên phải: 45
        x = (n // pow_val) % 10    # Chữ số đang xét: 3
        l = n // (pow_val * 10)    # Phần bên trái: 12

        # 1. Tổng các chữ số từ 1-9 trong các chu kỳ đầy đủ (l lần)
        # Mỗi chữ số 1-9 xuất hiện pow_val lần trong mỗi chu kỳ
        # Tổng 1->9 là 45
        res += l * pow_val * 45

        # 2. Đóng góp của chính chữ số x tại hàng hiện tại
        # Chữ số x xuất hiện (r + 1) lần (từ x00...0 đến xRR...R)
        res += x * (r + 1)

        # 3. Đóng góp của các chữ số từ 1 đến (x-1) tại hàng hiện tại
        # Mỗi chữ số này xuất hiện trọn vẹn pow_val lần
        # Tổng dãy số từ 1 đến x-1 là: x*(x-1)//2
        res += (x * (x - 1) // 2) * pow_val

        # Chuyển sang hàng tiếp theo bên trái
        pow_val *= 10

    print(res)

if __name__ == "__main__":
    solve()