Квадраты Кара-Балты
В Кара-Балте выкладывают плиткой квадратные дворики. Инженер Мирлан изучает «остаточные» квадраты: при данных 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; для разложения больших чисел подойдёт алгоритм Полларда (ро-метод).
Комментарии