如何计算可被数字总和整除的数字？

Question

以下是hackerearth提出的问题.这是问题问题的链接 !我在java和c中编写了它的解决方案,但是在提交的某些测试用例中超出了时间限制.没有参与者能够为所有测试用例解决这个问题.什么是最有效的解决方案？

题:

鲍勃喜欢DSD Numbers.DSD Number是一个可以用十进制表示的数字和整除的数字.

digitSum(n):n的位数之和(以十进制表示形式)

例如:n = 1234然后digitSum(n)= 1 + 2 + 3 + 4 = 10

DSD Number是数字n,使得n%digitSum(n)等于0

Bob要求Alice告诉范围[L,R]的DSD号码的数量.

约束:

1 <=测试用例<= 50

1 <= L <= R <= 10 ^ 9

样本输入

4
2 5
1 10
20 45
1 100

样本输出

4
10
9
33

Java中的代码:

class DSD {

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new    InputStreamReader(System.in));
    PrintWriter out=new PrintWriter(System.out);
    int t=Integer.parseInt(br.readLine());
    while(t-->0){
    StringTokenizer st=new StringTokenizer(br.readLine());
    int L=Integer.parseInt(st.nextToken());
    int R=Integer.parseInt(st.nextToken());

    int count=0,sum=0,i=L,j=0;

    while(i>0){
    sum+=i%10;
    i=i/10;
    }
    if(L%sum==0)
        count++;
    for(i=L+1;i<=R;i++){
    if(i%10!=0){
    sum+=1;
    }
    else
    {
    j=i;
    while(j%10==0){
    sum-=9;
    j/=10;
    }
    sum+=1;
    }
    if(i%sum==0)
        count++;
    }
        out.println(count);
    }
    out.close();
} 
}

Answer 1

我们可以使用动态规划来解决这个问题。

观察：

• 每个数字最多有 10 位数字，因此每个数字的最大数字总和将小于 100。

因此，假设我们知道一个数字的数字之和，通过逐位处理，我们需要检查四件事：

• 当前数字是否大于下限。
• 当前数字是否小于上限。
• 当前数与其和的模是多少。
• 当前所有数字的总和是多少。

我们提出这个函数int count(int digit, boolean larger, boolean smaller, int left, int mod)，然后，dp 状态：dp[digit][larger][smaller][left][mod]。

对于每个测试用例，时间复杂度为number of possible sum^3 x number of digit = 100^3*10 = 10^7.

有 50 个测试用例 -> 50*10^7 = 5*10^8 操作，仍在时间限制内。

Java代码：

static int[][][][][] dp;
static int[][][][][] check;
static int cur = 0;

public static void main(String[] args) throws FileNotFoundException {
    // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
    // "output.txt")));
    PrintWriter out = new PrintWriter(System.out);
    Scanner in = new Scanner();


    int n = in.nextInt();
    dp = new int[11][2][2][82][82];
    check = new int[11][2][2][82][82];
    for (int i = 0; i < n; i++) {

        int l = in.nextInt();
        int r = in.nextInt();
        String L = "" + l;
        String R = "" + r;
        while (L.length() < R.length()) {
            L = "0" + L;
        }
        int result = 0;
        for (int j = 1; j <= 81; j++) {

            cur = cur + 1;
            result += count(0, 0, 0, j, 0, j, L, R);
        }
        out.println(result);
    }
    out.close();
}

public static int count(int index, int larger, int smaller, int left,
        int mod, int sum, String L, String R) {
    if (index == L.length()) {
        if (left == 0 && mod == 0) {
            return 1;
        }
        return 0;
    }
    if((L.length() - index) * 9 < left){
        return 0;
    }
    if (check[index][larger][smaller][left][mod] == cur) {
        return dp[index][larger][smaller][left][mod];
    }
    //System.out.println(cur);
    check[index][larger][smaller][left][mod] = cur;
    int x = L.charAt(index) - '0';
    int y = R.charAt(index) - '0';
    int result = 0;
    for (int i = 0; i < 10 && i <= left; i++) {

        if (x > i && larger == 0) {
            continue;
        }
        if (y < i && smaller == 0) {
            continue;
        }
        int nxtLarger = larger;
        int nxtSmaller = smaller;
        if (x < i) {
            nxtLarger = 1;
        }
        if (y > i) {
            nxtSmaller = 1;
        }
        int nxtMod = (mod * 10 + i) % sum;
        result += count(index + 1, nxtLarger, nxtSmaller, left - i, nxtMod,
                sum, L, R);
    }
    return dp[index][larger][smaller][left][mod] = result;
}

更新：我已经提交并通过了这个问题的所有测试用例，（解决这个问题的第二个人）这是我提交的链接