Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Задача про XOR

(Время: 1 сек. Память: 16 Мб Сложность: 69%)

В рамках подготовки к чемпионату мира Кирилл придумал Ане задачу. Он написал N знаковых 32-битных чисел и попросил вычислить значение некоторого выражения S. Пусть a1, …, aN - все эти числа. Тогда выражение это

S = (a1 xor a2 xor … xor an) xor (b1 xor b2 xor … xor bn-1),

где

bi = F(ai, ai+1) xor F(ai, ai+2) xor … xor F(ai, an).

В этой формуле под знаком xor понимается побитовое «исключающее или», а F(a, b) = x - 1, где x - максимальная степень двойки, на которую делится нацело a-b, если a ≠ b, и F(a, b) = -1, если a = b. Все операции xor выполняются слева направо, если скобки не указывают иной порядок.

Аня, как большая специалистка в области циклов, быстро написала требуемую программу, однако программа работала слишком долго. Чтобы лучше разобраться в этом вопросе, она попросила вас написать программу, которая бы укладывалась в отведенное время. Помогите ей это сделать.

Входные данные

В первой строке входного файла INPUT.TXT содержится число N (1 ≤ N ≤ 105). В следующих N строках содержится N 32-битных знаковых целых чисел ai по одному на строке.

Выходные данные

В выходной файл OUTPUT.TXT выведите значение выражения.

Примеры

INPUT.TXTOUTPUT.TXT
13
1
2
3
1
22
1
1
-1
33
1
2
4
6

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483