== include(page="template/taskheader" task_id="aiacucmmdc") ==

Poveste şi cerinţă...

Neştiind ce poveste să găsească pentru această problemă, autorul a decis să nu mai complice concurenţii cu texte inutile, care mai mult te încurcă atunci când citeşti cerinţa.
 
Astfel se dă un şir de $N$ numere naturale. Se cere să se determine numărul de subsecvenţe ale şirului, cu proprietatea că cmmdc-ul subsecvenţei este divizibil cu un număr natural $P$. Super simplu.
 
Prin subsecvenţă se înţelege o succesiune de unul sau mai multe elemente aflate pe poziţii consecutive în şirul iniţial.

h2. Date de intrare

Fişierul de intrare $aiacucmmdc.in$ ...

Fişierul de intrare $aiacucmmdc.in$ conţine pe prima linie un număr natural $N$ (acesta reprezentând numărul de elemente ale şirului) şi numărul natural $P$.
Pe următoarea linie se află $N$ numere naturale separate prin spaţiu, reprezentând elementele şirului.

h2. Date de ieşire

În fişierul de ieşire $aiacucmmdc.out$ ...

În fişierul de ieşire $aiacucmmdc.out$ va conţine pe prima linie un număr natural $K$, acesta reprezentând numărul de subsecvenţe cu proprietatea cerută.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* Prin cmmdc se înţelege cel mai mare divizor comun comun al numerelor respective.
* Prin definiţie, cel mai mare divizor comun al unui singur număr este chiar numărul însuşi.
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ a[i], P ≤ 2.000.000.000$
* Pentru teste în valoare de $10$ puncte $N ≤ 250$
* Pentru teste în valoare de $25$ de puncte $N ≤ 3000$
* Pentru teste în valoare de $50$ de puncte $N ≤ 10.000$ şi numărul de subsecvenţe nu va depăşi $1.500.000$
* Pentru teste în valoare de $90$ de puncte $N ≤ 1.000.000$
* Exemplele vor reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.
 

h2. Exemplu
table(example). |_. aiacucmmdc.in |_. aiacucmmdc.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 3
2 9 6 4 3 13
| 4

|
h3. Explicaţie

...

* $N = 6, P = 3$
* Cele $4$ subsecvenţe sunt:
* de la $2$ la $2 = {9} cu cmmdc = 9$
* de la $3$ la $3 = {6} cu cmmdc = 6$
* de la $2$ la $3 = {9, 6} cu cmmdc = 3$
* de la $5$ la $5 = {3} cu cmmdc = 3$

== include(page="template/taskfooter" task_id="aiacucmmdc") ==
 

== include(page="template/taskfooter" task_id="aiacucmmdc") ==