secvxor

Secvxor

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

Se consideră un şir $A$ cu $N$ elemente numere naturale nenule. Pentru fiecare subsecventă de forma $A{~i~}, A{~i+1~}, A{~i+2~}, ..., A{~j~}$ din şirul $A$ (unde $i < j$) pentru care cel mai mare divizor comun al numerelor $A{~i~}$ şi $A{~j~}$ este mai mare decât $1$, se calculează valoarea $A{~i~} &#x2295; A{~i+1~} &#x2295; ... &#x2295; A{~j~}$, unde &#x2295; este operaţia sau exclusiv pe biţi (notată în C/C++ cu $ˆ$). Între valorile obţinute pentru fiecare subsecventă se efectuează din nou operaţia $&#x2295;$, obţinând că rezultat un număr $B$.
 

Se consideră un şir $A$ cu $N$ elemente numere naturale nenule. Pentru fiecare subsecvenţă de forma $A{~i~}, A{~i+1~}, A{~i+2~}, ..., A{~j~}$ din şirul $A$ (unde $i < j$) pentru care cel mai mare divizor comun al numerelor $A{~i~}$ şi $A{~j~}$ este mai mare decât $1$, se calculează valoarea $A{~i~}$ &#x2295; $A{~i+1~}$ &#x2295; $...$ &#x2295; $A{~j~}$, unde &#x2295; este operaţia sau exclusiv pe biţi (notată în C/C++ cu $ˆ$). Între valorile obţinute pentru fiecare subsecventă se efectuează din nou operaţia &#x2295;, obţinând ca rezultat un număr $B$.

Se cere să se determine valoarea lui $B$.
h2. Date de intrare

Pe prima linie a fişierul de intrare $secvxor.în$ se află numărul $N$, iar pe a doua linie elementele şirului $A$.

Pe prima linie a fişierul de intrare $secvxor.in$ se află numărul $N$, iar pe a doua linie elementele şirului $A$.

h2. Date de ieşire
Pe prima linie a fişierul de ieşire $secvxor.out$ se va afişa valoarea numărului $B$.

h2. Restricţii
* $1 ≤ N ≤ 100 000$
* $1 ≤ A{~i~} ≤ 1 000 000$, pentru orice $i$ cu $1 ≤ i ≤ N$

h2. Subtaskuri

h2. Subtask-uri

table(restrictii). |_. # |_. Punctaj |_. Restricţii |

table(subtasks). |_. # |_. Punctaj |_. Restricţii |

| $1$ | $9$ | $1 ≤ N ≤ 500$ |
| $2$ | $12$ | $N ≤ 5 000$ |
| $3$ | $15$ | Elementele şirului $A$ sunt numere pare |

h3. Explicaţie

"Definitia operatiei $⊕$":https://en.wikipedia.org/wiki/Bitwise_operation#XOR

"Definitia operatiei ⊕":https://en.wikipedia.org/wiki/Bitwise_operation#XOR

Subsecventele care satisfac proprietatea din enunţ (adică sunt de lungime cel puţin $2$, iar elementele de la începutul şi sfârşitul subsecvenţei au cel mai mare divizor comun mai mare decât 1) sunt: $(4, 7, 6), (4, 7, 6, 10), (7, 6, 10, 21), (6, 10), (6, 10, 21)$. Efectuând operaţia $⊕$ între elementele fiecărei subsecvente obţinem valorile $5, 15, 30, 12$, respectiv $25$. Efectuând operaţia $⊕$ între aceste valori obţinem valoarea lui $B = 1$.

Subsecventele care satisfac proprietatea din enunţ (adică sunt de lungime cel puţin $2$, iar elementele de la începutul şi sfârşitul subsecvenţei au cel mai mare divizor comun mai mare decât 1) sunt: $(4, 7, 6), (4, 7, 6, 10), (7, 6, 10, 21), (6, 10), (6, 10, 21)$. Efectuând operaţia ⊕ între elementele fiecărei subsecvenţe obţinem valorile $5, 15, 30, 12$, respectiv $25$. Efectuând operaţia ⊕ între aceste valori obţinem valoarea lui $B = 1$.

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