Fişierul intrare/ieşire:divseq.in, divseq.outSursăAlgoritmiada 2016 - Runda 4 - Juniors
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.375 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.indivseq.out
4
1 6 2 10
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?