divseq

Divseq

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

Poveste şi cerinţă...

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.

h2. Date de intrare

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

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

h2. Date de ieşire

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

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

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 |

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

| 4
1 6 2 10
| 8

|

h3. Explicaţie
 
...
 

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