SOLVE
LATER
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} \)
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.