Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | secvxor.in, secvxor.out | Sursă | ONI 2023, Baraj Seniori, ziua 2 |
| Autor | Mihai Bunget | Adăugată de |  Voicu Mihai-Valeriu •cadmium_ |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Secvxor
Se consideră un şir A cu N elemente numere naturale nenule. Pentru fiecare subsecventă de forma Ai, Ai+1, Ai+2, ..., Aj din şirul A (unde i < j) pentru care cel mai mare divizor comun al numerelor Ai şi Aj este mai mare decât 1, se calculează valoarea Ai ⊕ Ai+1 ⊕ ... ⊕ Aj, unde ⊕ 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 ⊕, obţinând că rezultat un număr B.
Se cere să se determine valoarea lui B.
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.
Date de ieşire
Pe prima linie a fişierul de ieşire secvxor.out se va afişa valoarea numărului B.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ Ai ≤ 1 000 000, pentru orice i cu 1 ≤ i ≤ N
Subtaskuri
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 9 | 1 ≤ N ≤ 500 |
| 2 | 12 | N ≤ 5 000 |
| 3 | 15 | Elementele şirului A sunt numere pare |
| 4 | 26 | Elementele şirului A sunt numere prime |
| 6 | 38 | Fără restricţii suplimentare |
Exemplu
| secvxor.in | secvxor.out |
|---|---|
| 5 4 7 6 10 21 | 1 |
Explicaţie
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.
