Effective search algorithm if a very large number is divisible by 7

Question

So, this was a question on one of the problems that I encountered in an online contest, a few days ago.

Question:

Accept the two entrances.

• A large number of digits N ,
• The number of Q questions will be asked .

In each of the questions you need to find whether the number formed by the line between the indices L _i and R _{i will be} divided by 7 or not.

Input:

The first line comprises a number consisting of numbers N . The next line contains Q , indicating the number of questions. Each of the following lines Q contains 2 integers L _i and R _{i sub>.}

Conclusion:

For each question, type “YES” or “NO” if the number formed by the line between the indices L _i and R _i is divided by 7.

Limitations:

1 ≤ N ≤ 10 ⁵

1 ≤ Q ≤ 10 ⁵

1 ≤ L _i , R _i ≤ N

Input Example:

357753
3
1 2
2 3
4 4

Output result:

YES
NO YES

:

35, 7.

---

: 1,0 .

: 256

: 1024

---

:

, , , .. 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)

- 7,

:
42,341,530 → 530 - 341 = 189 + 42 = 231 → 23 - (1 × 2) = 21

, , 1/3rd Q.N, .

---

- ? - ?

,

Answer 1

.

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 + 1}mod 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 + 1}mod 7 7 10.

:
O(N)
O(Q) + O(N)

2: " "
. node mod 7 , node.
, , 7 7 .
O(Q log N) + O(N log N)

Answer 2

, mod 7 , mod of number .

, :

• O (N) . 100 .
• , , . O (N) ( )

. 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 3

7 , 0 ( , 0% 7, 3% 7, 35% 7, 357% 7...), ( a, b) [a-1] [b], [b] 1-3-2-6-4-5 10 ^ X 7, (1+b-a)%6 . , YES, 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