[ol2] XORovanje delilaca

Xorovanie deliteľov - st

Kým bola Duňa v prírode a pozorovala líšky, našla odhodený papier, na ktorom bolo zapísané číslo n a potom k rôznych čísel d₁, d₂, …, d_k. Tieto čísla sa jej zdali zaujímavé, a tak sa pokúsila zistiť ich význam. Zistila, že množina {d₁, d₂, …, d_k} je práve množina všetkých deliteľov čísla n. Inými slovami, pre každé 1 ≤ i ≤ k platí, že dᵢ delí n. Zároveň platí, že pre každé kladné celé číslo x, ktoré delí n, existuje práve jeden index i, pre ktorý dᵢ = x. Funkcia xor_deliteľov(x) je exkluzívna disjunkcia všetkých deliteľov čísla x. Formálne, ak sú d₁, d₂, …, d_k všetci delitelia čísla x, potom: xor_deliteľov(x) = d₁ xor d₂ xor … xor d_k Duňa chce nájsť hodnoty funkcie xor_deliteľov pre všetky hodnoty d₁, d₂, …, d_k. Keďže je v prírode, nemá pri sebe počítač a čísla sú veľmi veľké, poprosila vás o pomoc.

Popis vstupu V prvom riadku sú dve čísla n a k – číslo n zo zadania a počet jeho deliteľov. V druhom riadku je k čísel d₁, d₂, …, d_k – všetci delitelia čísla n.

Popis výstupu V jednom riadku vypíšte k čísel. i-te z nich má byť hodnota xor_deliteľov(dᵢ).

Príklad 1 Vstup 1 1 1 Výstup 1 Vysvetlenie
Jediný deliteľ čísla 1 je 1, preto xor_deliteľov(1) = 1.

Príklad 2 Vstup 12 6 12 1 3 6 2 4 Výstup 14 1 2 6 3 7 Vysvetlenie Delitele čísla 12 sú 1, 2, 3, 4, 6 a 12, takže
xor_deliteľov(12) = 1 xor 2 xor 3 xor 4 xor 6 xor 12 = 14. Delitele čísla 1: {1} → výsledok 1
Delitele čísla 3: {1, 3} → 1 xor 3 = 2
Delitele čísla 6: {1, 2, 3, 6} → výsledok 6
Delitele čísla 2: {1, 2} → výsledok 3
Delitele čísla 4: {1, 2, 4} → výsledok 7

Obmedzenia • 1 ≤ n ≤ 10¹⁸ • 1 ≤ k ≤ 10⁵ • 1 ≤ dᵢ ≤ n • množina {d₁, …, d_k} je presne množina všetkých deliteľov čísla n • všetky dᵢ sú rôzne Testy sú rozdelené do 5 skupín: • 10 bodov: n ≤ 1 000 • 15 bodov: n ≤ 10⁵ • 15 bodov: n ≤ 10⁷ • 20 bodov: n ≤ 10⁹ • 40 bodov: bez ďalších obmedzení

Poznámka Operátor exkluzívnej disjunkcie je v Pascale označený xor, v C++ symbolom ^.
Operácia x xor y pre nezáporné celé čísla sa určí takto: čísla zapíšeme v binárnom tvare, doplníme úvodné nuly na rovnakú dĺžku a pre každý bit platí: • 0,0 → 0 • 0,1 → 1 • 1,0 → 1 • 1,1 → 0 Exkluzívna disjunkcia je komutatívna a asociatívna operácia: a xor b = b xor a
(a xor b) xor c = a xor (b xor c)