Special Substrings
Tag(s):

## Medium

Problem
Editorial
Analytics

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.

SAMPLE INPUT
10 324567
9207289341
SAMPLE OUTPUT
40

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, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

International Women's Hackathon

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > String Algorithms
• Data Structures > Arrays
• Algorithms > Dynamic Programming