Mike and Fraud
Tag(s):

## Easy-Medium, Math

Problem
Editorial
Analytics

Mike Ross is a fraud!. That's what the world says. However, Harvey is highly disagreeable to this, and feels that Mike did what he had to, only for the good of the world.

Tired of constant criticism, Harvey decides to prove to the world, what a great friend he is. Travis Tanner, being his Biggest competitor, challenges him to the following task :

Given an array A of size N and an integer K, can you find the number of good sub-arrays of this array? A sub-array is a contiguous subsequence of an array, and is considered to be good, if the product of all integers it contains is divisible by K.

Harvey is completely bowled over by the difficulty of this task, as he is not a very math oriented person, and needs your help urgently. Can you find the answer ?

Input Format :

The first line contains 2 space separated integers N and K. The next line contains N space separated integers denoting the elements of array A.

Output Format:

Print the required answer on a single line.

Constraints:

$1 \le N \le 2\times 10^5$

$1 \le K \le 10^{9}$

$1 \le A[i] \le 10^{9}$

SAMPLE INPUT
6 2
1 2 3 4 5 6
SAMPLE OUTPUT
18
Explanation

The subarray from 4 to 6 is one of the subarrays divisible by 2, as $4 \times 5 \times 6$=$120$. that is divisible by 2. In total, there are $18$ such subarrays.

Time Limit: 2.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

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

November Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Math > Number Theory
• Math > Number Theory
• Math > Combinatorics