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

Question

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

问题：

接受两个输入。

大数N位数，
要问的问题数Q。

在每道题中，你必须找出索引之间的字符串组成的数字是否为 L_i 和 R_i是否能被7整除

输入：

第一行包含由 N 位数字组成的数字。下一行包含 Q，表示问题的数量。接下来的 Q 行中的每一行都包含 2 个整数 L_i 和 R_i.

输出：

对于每个问题，打印"YES"或"NO"，如果索引之间的字符串组成的数字L_i 和 R _i能被7整除.

约束条件：

1≤N≤10⁵

1≤Q≤10⁵

1≤L_i,R_i≤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(Q.N)也可以认为是二次时间.因此，这超过了给定的时间限制并且效率不高。

第二次尝试：

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

我确实找到了一种名为 Pohlman–Mass 被 7 整除法 的算法，它建议

Using quick alternating additions and subtractions:
42,341,530 -> 530 − 341 = 189 + 42 = 231 -> 23 − (1×2) = 21 YES

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

我是不是漏掉了什么？谁能帮我找到有效解决这个问题的方法？

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

Answer 1

基本上，您希望能够在任何时候给定数字的 mod 计算任何数字的 mod 7。

你能做的是;

记录每个时间点 O(N) 的 modulo 和 space。最多使用 100 KB 内存。
在两个点处取 modulo 并确定在开始之前减去多少数字会使例如O(N) 时间和 space（一次不是每个循环）

例如介于 2 和 3 之间

357 % 7 = 0
3 % 7 = 3 and 300 % 7 = 6 (the distance between the start and end)

和 0 != 6 所以这个数字不是 7 的倍数。

介于 4 和 4 之间

3577 % 7 == 0
357 % 7 = 0 and 0 * 10 % 7 = 0

因为 0 == 0 它是 7 的倍数。

Answer 2

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

1：动态规划方法
让输入为数字数组 A[N].
设 N[L,R] 是由数字 L to R.
组成的数字设另一个数组为 M[N]，其中 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^R-L+1+ N[L,R]
implies (N[1,R] mod 7) = (N[1,L-1] mod 7 * (10^R-L+1mod 7)) + (N[L,R] mod 7)
implies N[L,R] mod 7 = (M[R] - M[L-1] * (10^R-L+1 mod 7)) mod 7

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

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

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

Answer 3

您首先为每个以 0 偏移量开头的数字构建一个模 7 的数字列表（如您的情况，0%7、3%7、35%7、357%7...），然后针对每种情况的 (a,b) 抓取数字 [a-1] 和数字 [b]，然后将数字 [b] 乘以由 [=13= 定义的 10^X 模 7 的 1-3-2-6-4-5 序列] 并进行比较。如果它们相等，return YES，否则 return NO。一个伪代码：

readString(big);
Array a=[0]; // initial value
Array tens=[1,3,2,6,4,5]; // quick multiplier lookup table
int d=0;
int l=big.length;
for (int i=0;i<l;i++) {
    int c=((int)big[i])-48; // '0' -> 0, and "big" has characters
    d=(3*d+c)%7;
    a.push(d); // add to tail
}
readInt(q);
for (i=0;i<q;i++) {
    readInt(li);
    readInt(ri); // get question
    int left=(a[li-1]*tens[(1+ri-li)%6])%7;
    if (left==a[ri]) print("YES"); else print("NO");
}

一个测试例子：

247761901
1
5 9

61901 % 7=0。正在计算：

a = [0 2 3 2 6 3 3 4 5 2]
li = 5
ri = 9
left=(a[5-1]*tens[(1+9-5)%6])%7 = (6*5)%7 = 30%7 = 2
a[ri]=2
Answer: YES

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

Effiecient Algorithm for Finding if a Very Big Number is Divisible by 7

java

algorithm

dynamic-programming

division

time-complexity