Editorial for Digit Sum

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Let $f(N)$ ~f(N)~ be the number of integers $x$ ~x~ with $0 \le x \le N$ ~0 \le x \le N~ whose digit sum is divisible by $M$ ~M~. The answer is $f(R) - f(L - 1)$ ~f(R) - f(L - 1)~.

To compute $f(N)$ ~f(N)~, process the digits of $N$ ~N~ from left to right. Keep counts for numbers that are already strictly smaller than the prefix of $N$ ~N~, grouped by their digit-sum remainder modulo $M$ ~M~. Also keep the current remainder of the one prefix that is still exactly equal to $N$ ~N~'s prefix.

When reading a new digit with limit $d$ ~d~, any already-smaller prefix can append any digit from $0$ ~0~ to $9$ ~9~. The tight prefix can append digits from $0$ ~0~ to $d - 1$ ~d - 1~ to become smaller, or append $d$ ~d~ to remain tight. At the end, all smaller prefixes with remainder $0$ ~0~ count, and the tight number $N$ ~N~ itself counts if its remainder is $0$ ~0~.

This takes $O(|R| \cdot M \cdot 10)$ ~O(|R| \cdot M \cdot 10)~ time.

Solution (Python)

import sys


def subtract_one(s):
    if s == "0":
        return None

    digits = list(s)
    i = len(digits) - 1
    while digits[i] == "0":
        digits[i] = "9"
        i -= 1
    digits[i] = str(int(digits[i]) - 1)

    result = "".join(digits).lstrip("0")
    return result or "0"


def count_up_to(n, m):
    if n is None:
        return 0

    loose = [0] * m
    tight_remainder = 0

    for ch in n:
        limit = ord(ch) - ord("0")
        next_loose = [0] * m

        for remainder, count in enumerate(loose):
            if count == 0:
                continue
            for digit in range(10):
                next_loose[(remainder + digit) % m] += count

        for digit in range(limit):
            next_loose[(tight_remainder + digit) % m] += 1

        loose = next_loose
        tight_remainder = (tight_remainder + limit) % m

    return loose[0] + (1 if tight_remainder == 0 else 0)


def main() -> None:
    tokens = sys.stdin.read().split()
    l, r, m_str = tokens
    m = int(m_str)

    answer = count_up_to(r, m) - count_up_to(subtract_one(l), m)
    print(answer)


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.