Entering edit mode

Click here to Practice

Submit Problem to OJ

We are given a integer p and two large numbers in the form of string L and R. We need to count the no of values between L and R (both inclusive) that are **divisible by the p** and number should have **even value at the odd indices** and **odd values in the even indices**.

**Constraints:**

- 1 <= p <= 25
- 1 <= L,R< 10^99

**Example:**

**Input:**

p=7 L=1 R=25

**Output:**

2

7,14,21

7- at 0 index(even) we have value 7(odd).

14 - At 0 index we have value 4 which is even, so do not count

21 - 0 index have value 1 and index-1 have value 2.

index 0 starts at the right most position of the value.

Odd Even Prime Multiples :Humans have finally made contact with aliens from outer space who call themselves Primes. Naturally, each of their individuals

loves prime numbers. Their emperor loves the prime number p the most. However, their maths is much more advanced than the version we use on Earth. They have very long numbers with several digits going up to 100 digits. A number is said to be valid for them if it follows the following conditions:

The number must be divisible by the prime number p to keep the emperor happy.

Even indices must have odd digits, and odd indices must have even digits. Indexing starts from the right end. For example, in the number 123, 3 is at index 0, 2 is at index 1, and 1 is at index 2. Hence if this number is divisible by p,then it can be a valid number.

The number must not have leading zeroes.

Task

The emperor has sent the message that he will consider humansan intelligent life form if you can tell him the number of valid

numbers between L and R (both inclusive). Since the number of

such numbers can be too large, you only need to tell the answer modulo (10^{9}+7).

**Assumptions**

• p = 7

• 1 = 5

• R = 25

**Approach**

• One condition of validity is that the number should be

divisible by p (7 in this case). Only the numbers 7, 14, and 21

satisfy this condition in the given range.

Digit at index 1 | Digit at index 0 | |

number = 7 | - | 7 |

number = 14 | 1 | 4 |

number = 21 | 2 | 1 |

You can observe the following from the table:

• 7 is a valid number as the digit at the even index is odd.

• 14 is not a valid number as the digit at index O is 4, which is even

• 21 is a valid number as the digit at index O is odd, and the digit at index 1 is even.

Hence, the answer to this case is 2.

**Function description**

Complete the countPrimeMultiples function provided in the editor. This function takes the following 3 parameters and returns an integer, i.e., the count of such valid numbers in the given range:

• p: Represents the prime number of the emperor

• L: Represents the lower limit of the range of numbers

• R: Represents the upper limit of the range of numbers

**Input format**

Note: This is the input format you must use to provide custom

input (available above the Compile and Test button).

• The first line contains T denoting the number of test

cases. T also specifies the number of times you have to run

the countPrimeMultiples function on a different set of

inputs.

For each test race

- The first line contains an integer p denoting the primenumber of the emperor. It is guaranteed to be a prime number.
- The Second line contains a string L denoting the lower limit.
- The third line contains a String R denoting the upper limit.

**Output Format**

For each test case in a new line, print a single line containing an

integer modulo (109+7) representing the answer.

Constraints

1 < T < 20

1 ≤ p ≤ 2500

1 ≤ L ≤ R<10^{99}

Entering edit mode

Since the range of the numbers are of order 10⁹⁹, checking for each number would give TLE. It can be observed that *p* is small. This problem can be solved by digit dp. Let the answer for the numbers between 0 to *x* be *f(x)*, so we will need to calculate *f(R)-f(L-1)*. As *L* is given in the form of string, to get *L-1*, we will iterate backward till we don’t find a non zero digit, and decrease it by 1, and all the zeros in the ending would be made 9.

Now coming to the dp transition. Let’s calculate *f(x)*. The states of the dp would be *index*, *remainder*, *tight*, and *startStatus*.

*index*signifies the current index of the number being formed.*remainder*signifies the remainder of the number formed so far.*tight*would take value 0 or 1, representing if the prefix of the number formed is equal to prefix of*x*.*startStatus*will take values 0,1 or 2. 0 represents that all the previous digits of the number are 0 (it would be helpful when the length of the final number formed is less than the length of x). 1 represents that all the previous digits of the number are 0, and we will start forming the number at the current index. 2 represents that the number has already some non zero digits in it.

So, when *tight* is 1, we cannot place a number greater than the digit at the current index in x. And if we place a smaller digit than the digit at the current index in x, *tight* will become 0.

If the *startStatus* is 1, we cannot place 0 at the current index, but if *startStatus* is 2, we can place 0 at the current index. For each index, we will check if the parity of the index is odd, we will place even digits, else we will place odd digits.

The time and space complexity will be `O(n*p)`

, where n is the length of the string.

```
dp[100][25][2][3]
mod = 1e9+7
solve(idx, rem, tight, startstatus, p, x)
if (idx == num.size())
return (rem == 0 && startstatus > 0)
if (dp[idx][rem][tight][startstatus] != -1)
return dp[idx][rem][tight][startstatus]
if (startstatus > 0) {
ans = 0, i = 1
if((num.size() % 2) == (idx % 2))
i = 2
if(startstatus == 2)
i = 0
if(!tight){
for(; i < 10; i += 2)
ans += solve(idx + 1, (rem * 10 + i) % p, tight, 2, p, num)
else
for(; i < num[idx] - '0'; i += 2)
ans += solve(idx + 1,(rem * 10 + i) % p, 0, 2, p, num)
if(i == num[idx] - '0')
ans += solve(idx + 1,(rem * 10 + i) % p, 1, 2, p, num)
return dp[idx][rem][tight][startstatus] = ans;
} else {
option1 = solve(idx, rem, idx == 0 ? 1 : 0, 1, p, num)
option2 = solve(idx + 1, rem, tight, 0, p, num)
return dp[idx][rem][tight][startstatus] = option1 + option2
}
```

Bro can u send the complete code