Два стада на перевале


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На перевале Тоо-Ашуу пастухи Азамат и Тилек коротают вечер за игрой. Перед ними две кучки камешков: в первой a камешков, во второй b. Игроки ходят по очереди, начинает Азамат. За ход можно:

  • взять любое положительное число камешков из первой кучки;
  • или взять любое положительное число камешков из второй кучки;
  • или взять одно и то же положительное число камешков из обеих кучек сразу.

Кто не может сделать ход (обе кучки пусты), тот проиграл.

Рисунок

Ходы различаются кучкой (первая, вторая или обе) и числом взятых камешков. Для каждой из T позиций найдите количество выигрывающих ходов Азамата — таких, после которых Тилек при любой его игре проигрывает. Если таких ходов нет, Азамат проигрывает, и нужно вывести 0.

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

В первой строке — число T (1 ≤ T ≤ 10⁵). В каждой из следующих T строк — два целых числа a и b (0 ≤ a, b ≤ 10¹⁸).

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

Для каждой позиции выведите количество выигрывающих ходов.

Пример 1

Вход:

5
3 3
2 2
3 5
10 6
0 7

Выход:

1
3
0
0
1

Пояснение

Проигрышные позиции (кто должен из них ходить, тот проигрывает при правильной игре соперника): (0, 0), (1, 2), (3, 5), (4, 7), (6, 10), … и симметричные им. Из (3, 3) выигрывает только ход «взять по 3 из обеих кучек» — в (0, 0). Из (2, 2) выигрывающих ходов три: в (0, 0), а также взять 1 камешек из одной из кучек — в (1, 2) или (2, 1).

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов a, b ≤ 150, ещё в 5 % тестов a, b ≤ 10⁶.

Подсказка

Теорема Битти: если α, β > 1 иррациональны и 1/α + 1/β = 1, то последовательности ⌊nα⌋ и ⌊nβ⌋ (n ≥ 1) вместе содержат каждое натуральное число ровно один раз.


Комментарии

Еще нет ни одного комментария.