eolymp
bolt
Try our new interface for solving problems
Məsələlər

Квадратный корень

Квадратный корень

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Число x называется квадратным корнем числа a по модулю n тогда и только тогда, когда x^2 = a (mod n). Напишите программу, которая находит все квадратные корни числа a по модулю n.

Giriş verilənləri

В первой строке находится одно число t (1t100000) — количество тестов. Каждая следующая строка представляет собой отдельный тест, который содержит целые числа a и n (1a, n32767, n — простое, a и n — взаимно простые).

Çıxış verilənləri

Для каждого теста выведите все квадратные корни a в диапазоне [0, n-1] в возрастающем порядке в одной строке, разделяя одним пробелом. Если для текущего теста корней не существует, выведите в отдельной строке сообщение "No root".

Nümunə

Giriş verilənləri #1
4
1 7
2 7
3 7
4 7
Çıxış verilənləri #1
1 6
3 4
No root
2 5
Mənbə III International Summer School Programming in Sevastopol 2012