Revizia anterioară Revizia următoare
| 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
Se vor acorda 10 puncte din oficiu
Exemplu
| aiacucmmdc.in | aiacucmmdc.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
