Python 代码

import sys

N = 12

def dp(n):
    if n == 0: return 1
    nums = []
    while n:
        nums.append(n % 10)
        n //= 10
    res, last = 0, 0
    for i in range(len(nums)-1, -1, -1):
        num = nums[i]
        for j in range(num):
            res += f[i+1][j][-last % K]
        last += num
        if i == 0 and last % K == 0: res += 1
    return res

while True:
    line = sys.stdin.readline()
    if line == '': break
    L, R, K = map(int, line.split())
    f = [[[0] * K for _ in range(10)] for _ in range(N)]
    for i in range(10): f[1][i][i % K] += 1
    for i in range(2, N):
        for j in range(10):
            for k in range(K):
                for t in range(10):
                    f[i][j][k] += f[i-1][t][(k-j) % K]
    print(dp(R) - dp(L-1))