Zero's Number 怎么来写

Question

Problem Description
Xnozero is very interested in k-divide number.

A way of k-divide on a number is defined as if number N can be divide into two parts m, n, and the sum of m and n can be divided by k, then this is a way of k-divide number based k.

For example, 3 + 33 = 36 is a way of 3-divide on number 333, as you can only divide 333 into 3 and 33, and the sum of 3 and 33 is 36, which can be divided by 3.

Zero's number is defined as f(n,k), and f(n,k) is the number of ways of n divided into k-divide numbers.

As defined above, 333 can be divided into two parts in two ways 3|33 and 33|3, so f(333,3)=2.

Now give you A, B, K, can you help Xnozero compute the sum of f(i,K) (A≤i≤B)? (1 ≤ K ≤ 20, 10 ≤ A ≤ B ≤ 1017)

Input
Multiple cases, process to the end of file.
Each line contains 3 integers A,B,K as descripted above.

Output
Output the sum of f(i,k), one per line.

Sample Input
333 333 3
10 100 2

Sample Output
2
46

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# import all necessary libraries
import numpy as np
from scipy.sparse.csgraph import dijkstra
from collections import defaultdict


class ZeroNumber:
    def __init__(self):
        self.f = defaultdict(int)
        self.dp = [[0 for _ in range(self.k)] for _ in range(self.n)]
        self.dfs()

    def dfs(self):
        for i in range(self.A, self.B+1):
            for j in range(self.K):
                if self.is_divide(i, j):
                    self.f[i] += 1
                    self.dp[self.F[j]][j] += 1

    def is_divide(self, n, k):
        for i in range(k):
            m = n // i
            if m * i != n or m % k != 0:
                return False
        return True

    @staticmethod
    def F(j):
        return max(0, j - k + 1)


if __name__ == "__main__":
    zero_number = ZeroNumber()
    while True:
        A, B, K = map(int, input().split())
        if A == B == 0:
            break
        print(zero_number.f[A])