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,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic,
Kotlin