Securitate

Cerință

O firmă de securitate IT monitorizează funcționarea unui sistem informatic. În fiecare zi, sistemul generează un cod numeric care reprezintă o cheie de acces.

Firma definește nivelul de securitate al unei zile ca fiind numărul de divizori primi distincți ai cheii de acces generate în acea zi. De exemplu, dacă s-a generat cheia de acces 12, atunci nivelul de securitate este 2, deoarece 12 are doi divizori primi distincți: 2 și 3.

Se cunosc cheile de acces generate pentru $N$ zile consecutive: $X_1, X_2, \ldots, X_N$.

O secvență de zile consecutive se numește perioadă vulnerabilă dacă toate cheile de acces din acea secvență au același nivel de securitate.

Scrieți un program care, cunoscând $N$, $K$ și șirul de chei de acces:

1. determină numărul de zile pentru care nivelul de securitate este exact $K$;
2. determină lungimea maximă a unei perioade vulnerabile de securitate și numărul perioadelor vulnerabile care au această lungime maximă.

Date de intrare

Fișierul de intrare securitate.in conține pe prima linie un număr natural $c$, reprezentând cerința care trebuie rezolvată ($1$ sau $2$).

Pentru cerința 1 ($c = 1$):

• pe a doua linie: $N$ și $K$, separate prin spațiu;
• pe a treia linie: cheile de acces generate pentru cele $N$ zile, separate prin câte un spațiu.

Pentru cerința 2 ($c = 2$):

• pe a doua linie: $N$;
• pe a treia linie: cheile de acces generate pentru cele $N$ zile, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire securitate.out va conține:

• Pentru $c = 1$: un număr natural, reprezentând numărul de zile pentru care nivelul de securitate este exact $K$;
• Pentru $c = 2$: două numere naturale $L$ și $NR$, separate prin spațiu, unde $L$ este lungimea maximă a unei perioade vulnerabile, iar $NR$ este numărul perioadelor vulnerabile de lungime maximă.

Restricții și precizări

• $1 \leq N \leq 500\ 000$;
• $1 \leq K \leq 7$;
• $1 \leq X_i \leq 1\ 000\ 000$, pentru oricare $1 \leq i \leq N$;
• O secvență dintr-un șir este formată din elemente aflate pe poziții consecutive în șirul dat;
• Cheia de acces 1 are nivelul de securitate 0;

Exemplul 1

securitate.in

1
6 2
30 12 17 18 40 3300

securitate.out

3

Explicație

Cele 6 chei de acces au următorii divizori primi distincți:

• 30 are 3 divizori primi (2, 3, 5)
• 12 are 2 divizori primi (2, 3)
• 17 are 1 divizor prim (17)
• 18 are 2 divizori primi (2, 3)
• 40 are 2 divizori primi (2, 5)
• 3300 are 4 divizori primi (2, 3, 5, 11)

Sunt 3 numere care au exact $K = 2$ divizori primi: 12, 18 și 40.

Exemplul 2

securitate.in

2
9
17 18 10 40 3300 30 66 105 3

securitate.out

3 2

Explicație

Cele 9 numere au următoarele niveluri de securitate: 1, 2, 2, 2, 4, 3, 3, 3, 1.

Lungimea maximă a unei perioade vulnerabile este 3, și există două secvențe vulnerabile de lungime maximă: (18, 10, 40) cu nivelul 2 și (30, 66, 105) cu nivelul 3.