查找非常大的数是否可以被 7 整除的有效算法

Question

所以这是关于几天前我在在线比赛中遇到的挑战之一的问题。

题：

接受两个输入。

1. 大量的N位数，
2. 要问的问题数Q。

在每个这个问题时，你必须找到如果由索引之间的字符串所形成的数大号_我和- [R_我是由7或不能整除。

输入：

第一行包含由N位数字组成的数字。下一行包含Q，表示问题的数量。每个下一个的Q线包含2个整数大号_我和- [R_我。

输出：

对于每个问题，打印“YES”或“NO”时，如果由索引之间的字符串所形成的数大号_我和- [R_我是由7整除。

约束：

1 ? 否 10 ⁵

1 ? 问？10 ⁵

1 ? 大号_我，R_我？N

样本输入：

357753
3
1 2
2 3
4 4

示例输出：

是
否
是

解释：

对于第一个查询，数字将是 35，显然可以被 7 整除。

---

时间限制：每个输入文件 1.0 秒。

内存限制： 256 MB

源限制： 1024 KB

---

我的方法：

现在根据约束条件，数字的最大长度即N可以达到10 ⁵。这么大的数字无法放入数字数据结构中，我很确定这不是解决它的有效方法。

第一次尝试：

我想到了这个算法来将除法的通用规则应用于数字的每个数字。这将用于检查任何两个数字之间的可分性，线性时间，即O(N)。

static String isDivisibleBy(String theIndexedNumber, int divisiblityNo){

    int moduloValue = 0;

    for(int i = 0; i < theIndexedNumber.length(); i++){

        moduloValue = moduloValue * 10;
        moduloValue += Character.getNumericValue(theIndexedNumber.charAt(i));
        moduloValue %= divisiblityNo;
    }

    if(moduloValue == 0){
        return "YES";
    } else{
        return "NO";
    }

}

但在这种情况下，算法还必须遍历Q 的所有值，也可以达到10 ⁵。

因此，解决问题所花费的时间变为O(QN)，也可以认为是二次时间。因此，这超过了给定的时间限制并且效率不高。

第二次尝试：

在那之后不起作用，我尝试搜索7的整除规则。我发现的所有这些都涉及基于数字的每个数字的计算。因此，这将再次导致线性时间算法。因此，结合问题的数量，它将等于二次时间，即 O(QN)

我确实找到了一种名为Pohlman-Mass 被 7 整除的算法，它表明

使用快速交替加减法：
42,341,530 -> 530 ? 341 = 189 + 42 = 231 -> 23？(1×2) = 21 是

但所做的只是将时间设为 1/3 的 QN，这并没有多大帮助。

---

我在这里错过了什么吗？谁能帮我找到有效解决这个问题的方法？

另外，这是否有可能是动态规划问题？

Answer 1

有两种方法可以解决这个问题。

1：动态规划方法
设输入为数字数组A[N]。
令N[L,R]为 由数字 组成的数字L to R。
设另一个数组为M[N]where M[i] = N[1,i] mod 7。
所以M[i+1] = ((M[i] * 10) mod 7 + A[i+1] mod 7) mod 7
预先计算数组M。

现在考虑这个表达式。
N[1,R] = N[1,L-1] *10^右-左+1 + N[L,R]
implies (N[1,R] mod 7) = (N[1,L-1] mod 7 * (10^右-左+1)mod 7)) + (N[L,R] mod 7)
implies N[L,R] mod 7 = (M[R] - M[L-1] * (10^右-左+1 mod 7)) mod 7

N[L,R] mod 7给出您的答案，并且可以进行计算，O(1)因为表达式右侧的所有值都已经存在。对于 10 ^R-L+1 mod 7，您可以预先计算 10 的所有幂的模 7。

时间复杂度： 总体
预先计算O(N)
O(Q) + O(N)

2：分治法
这是一种线段树解决方案。在每个树节点上，您存储该节点中数字形成的数字的 mod 7。
第一种方法中给出的表达式可用于通过组合两个子项的 mod 7 值来找到父项的 mod 7。
该解决方案的时间复杂度为O(Q log N) + O(N log N)