9098. XOR сумма

Вычислите XOR всех чисел на отрезке [l, r].

Вход. Два целых числа l и r (0 ≤ l ≤ r ≤ 10¹⁸).

Выход. Выведите значение XOR всех чисел на отрезке [l, r].

Пример входа	Пример выхода
3 8	11

РЕШЕНИЕ

математика

Анализ алгоритма

XOR четного и следующего за ним нечетного числа равен 1. Следовательно XOR четырех последовательных чисел, начиная с четного, равен 0. Таким образом XOR на промежутке [4a, 4a + 1, … 4b + 2, 4b + 3], где a ≤ b, равен 0.

Разобьём интервал [l, r] на три:

[l, r] = [l, 4a – 1] U [4a, 4a + 1, … 4b + 2, 4b + 3] U [4b + 4, r],

где

· 4a – наименьшее число, не меньшее l, делящееся на 4,

· 4b + 3 – наибольшее число, не большее r, при делении на 4 дающее остаток 3

XOR среднего интервала равен 0. XOR первого и последнего интервала вычисляем непосредственно.

Второе решение. XOR на промежутке [l, r] может быть вычислен как XOR на промежутке [0, r] ⊕ XOR на промежутке [0, l – 1] или то же самое что

XOR([l, r]) = XOR([0, r]) ⊕ XOR([0, l – 1])

Пусть f(n) = XOR([0, n]). Тогда

· f(n) = 0, если n ≤ 0;

· f(n) = n, если n делится на 4;

· f(n) = 1, если при делении n на 4 получается остаток 1;

· f(n) = n XOR 1, если при делении n на 4 получается остаток 2;

· f(n) = 0, если при делении n на 4 получается остаток 3;

Пример

Рассмотрим интервал [2; 12] = [2; 3] U [4; 11] U [12]. Тогда

XOR([2; 12]) = XOR([2; 3]) ⊕ XOR([4; 11]) ⊕ XOR([12]) =

2 ⊕ 3 ⊕ 0 ⊕ 12 = 0010₂ ⊕ 0011₂ ⊕ 0000₂ ⊕ 1100₂ = 1101₂ = 13

Второй способ

XOR([2; 12]) = XOR([0; 12]) ⊕ XOR([0; 1]) = 12 ⊕ 1 = 13

Реализация алгоритма

Читаем входные данные. В переменной res подсчитываем искомый XOR.

scanf("%lld %lld", &l, &r);

res = 0;

Двигаем левый конец l вперед, пока он не достигнет числа, делящегося на 4.

while (l % 4 != 0 && l <= r)

{

res ^= l;

l++;

}

Двигаем правй конец r назад, пока он не достигнет числа, которое приделении на 4 дает остаток 3.

while (r % 4 != 3 && l <= r)

{

res ^= r;

r--;

}

Выводим ответ.

printf("%lld\n", res);

Реализация алгоритма – XOR([l, r]) = XOR([0, r]) ⊕ XOR([0, l – 1])

#include <stdio.h>

long long i, l, r, res;

long long f(long long n)

{

if (n <= 0) return 0;

if (n % 4 == 0) return n;

if (n % 4 == 1) return 1;

if (n % 4 == 2) return n ^ 1;

return 0;

}

int main()

{

scanf("%lld %lld", &l, &r);

res = f(r) ^ f(l - 1);

printf("%lld\n", res);

}