Fişierul intrare/ieşire:	aiacucmmdc.in, aiacucmmdc.out	Sursă	Grigore Moisil 2017, 9
Autor	Sebastian Nechita	Adăugată de	Grigore Moisil •grigore.moisil
Timp execuţie pe test	0.3 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Aiacucmmdc

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.

Date de intrare

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.

Date de ieşire

Î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ă.

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.

Exemplu

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

Cum se trimit solutii?