Budget: values 10^18

**Tình huống.** Count integers in [1, N] with N ≤ 10^18 whose digit sum is divisible by 9. **Thuật toán nào phù hợp nhất? Chương trình chỉ cần in ra chữ cái.** **A)** Iterate 1..N checking each **B)** Sieve of Eratosthenes up to N **C)** Digit DP: state = position + digit-sum mod 9 **D)** Fenwick tree over digits