Квадраты Кара-Балты


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

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

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

В Кара-Балте выкладывают плиткой квадратные дворики. Инженер Мирлан изучает «остаточные» квадраты: при данных a и m его интересуют все целые x, 0 ≤ x < m, для которых x² при делении на m даёт остаток a:

x² ≡ a (mod m).

Рисунок

Для каждого из T вопросов найдите количество таких x.

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

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

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

Для каждого вопроса выведите количество решений.

Пример 1

Вход:

5
1 8
0 8
3 8
4 15
0 1

Выход:

4
2
0
4
1

Пояснение

По модулю 8 квадраты чисел 0, 1, …, 7 дают остатки 0, 1, 4, 1, 0, 1, 4, 1: остаток 1 получается четыре раза, остаток 0 — два раза, остаток 3 — ни разу. По модулю 15 остаток 4 дают числа 2, 7, 8, 13.

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

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 3000, ещё в 5 % тестов m ≤ 10⁹.

Подсказка

Китайская теорема об остатках позволяет решать задачу отдельно для каждой степени простого делителя m; для разложения больших чисел подойдёт алгоритм Полларда (ро-метод).


Комментарии

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