All Tracks Math Number Theory Problem

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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

International Women's Hackathon

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications