Special Substrings
Two positive integers are said to be relatively prime if their greatest common divisor is equal to 1. You will be given a string of digits S and an integer M. We call a substring, T, of S special if T and M are relatively prime. Your task is to count the number of special substrings of S.
Notes:
- A substring of S is a contiguous segment of S (the entire string counts as a substring too).
- Special substrings are allowed to have any number of leading zeros and they count as distinct special substrings.
- In this problem, a substring is to be interpreted as an integer.
Input:
The first line contains two integers: N \((1 \le N \le 10^3)\), the length of the string and an integer M \((1 \le M \le 10^9)\). The second line contains a string S of length N. You can safely assume that S contains digits only.
Output:
Print he number of special substrings of S.
Explanation
- 92, 07, 7, and 72893 are examples of special substrings. These are not the only special substrings in the sample input.
- 728934 is an example of a substring which is not special.
Time Limit:
1.0 sec(s)
for each input file.
Memory Limit:
256 MB
Source Limit:
1024 KB
Marking Scheme:
Marks are awarded when all the testcases pass.
Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic