Card Game Again
Contest: Educational Codeforces Round 24
Difficulty rating: 1900
Tags: binary search, data structures, number theory, two pointers

Vova again tries to play some computer card game.

The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number ai is written on the i-th card in the deck.

After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck.

Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?

Input format:
The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the cards.

Output format:
Print the number of ways to choose x and y so the resulting deck is valid.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example the possible values of x and y are:

1. x = 0, y = 0;
2. x = 1, y = 0;
3. x = 2, y = 0;
4. x = 0, y = 1.

Example input:
3 4
6 2 8

Example output:
4

Example input:
3 6
9 1 14

Example output:
1

Editorial:
Let's use two pointers.
Firstly you need to learn to factorize any number in no more than $${\mathcal {O}}(\log n)$$. We don't actually need any of their prime divisors except for those that are presented in k. So let's factorize k in $${\mathcal{O}}({\sqrt {10^{9}}})$$. After that check for the maximum power of each useful prime will work in $$O(\log 10^9)$$ for each number.
Now notice that if some segment [l, r] has its product divisible by k then all segments [l, i] for (r ≤ i ≤ n) will also have products divisible by k.
Now we have to find the smallest r for each l out there. That's where two pointers kick in. Let's maintain the current product of the segment in factorized form (only useful primes), as in normal form its enormous. The power of some prime in this form is the sum of powers of this prime in all the numbers in the segment.
We firstly move the left border of the segment one step to the right and then keep moving the right border to the right until power of at least one prime number in the product is smaller than in k. It means that it is not divisible by k. Moving the left border means subtracting all the powers of useful primes of number al from the product and moving the right border is adding all the powers of useful primes of ar.
The first time we reach such a segment, we add (n - r) to answer (consider r 0-indexed).
Overall complexity: $${ \mathcal { O } } ( n \cdot \log MAXN + { \sqrt { MAXN } } )$$, where MAXN is up to 109.