Divseq

divseq

== include(page="template/taskheader" task_id="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.

Poveste şi cerinţă...

h2. 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$.

Fişierul de intrare $divseq.in$ ...

h2. 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ţ.

În fişierul de ieşire $divseq.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 250.000$
* $1 ≤ A[i] ≤ 10^12^$
* 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.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. divseq.in |_. divseq.out |

| 4
1 6 2 10
| 8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="divseq") ==