Fişierul intrare/ieşire: | divseq.in, divseq.out | Sursă | Algoritmiada 2016 - Runda 4 - Juniors |
Autor | Mihai Calancea | Adăugată de | |
Timp execuţie pe test | 0.375 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Divseq
Spunem că un şir de numere naturale este interesant dacă pentru oricare două numere distincte din acest şir, cel mai mic dintre ele îl divide pe cel mai mare. Dându-se un şir A de N elemente, ne întrebăm câte subsecvenţe ale sale sunt interesante.
Date de intrare
Fişierul de intrare divseq.in va conţine pe prima sa linie valoarea N. Cea de-a doua linie va conţine N numere naturale, elementele şirului A.
Date de ieşire
În fişierul de ieşire divseq.out se va afla o singură valoare, egală cu numărul de subsecvenţe ale lui A care sunt interesante, conform definiţiei din enunţ.
Restricţii
- 1 ≤ N ≤ 250.000
- 1 ≤ A[i] ≤ 1012
- Teste în valoare de 30 de puncte au N = 100.
- Teste în valoare de 20 de puncte au N = 1000.
- Un sir B este subsecventa al unui sir A daca acesta contine elemente aflate pe pozitii consecutive din sirul A.
- Doua subsecvente B1 si B2 se considera diferite daca incep sau se termina pe pozitii diferite.
Exemplu
divseq.in | divseq.out |
---|---|
4 1 6 2 10 | 8 |