4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе
Задача A. Найдите все пары
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Дано простое P, натуральное n и массив a размера n. Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на P что и сумма. Более формально, если выполняется условие x∗y mod P=(x+y) mod P то пара (x,y) считается хорошей. Найдите количество хороших пар в массиве.
Формат входного файла
В первой строке входного файла заданы два целых числа n (1<=n<=105) — количество чисел в массиве, P (2<=P<=109) — заданное простое число P.
Во второй строке входного файла заданы n чисел ai (0<=ai<=109) - i-число в массиве.
Формат выходного файла
Выведите одно целое число - количество хороших пар в массиве.
Система оценки
Данная задача содержит четыре подзадачи:
- 1<=n<=1000,2<=p<=1000. Оценивается в 20 баллов.
- 1<=n<=1000,p=2. Оценивается в 20 баллов.
- 1<=n<=100000,2<=p<=1000. Оценивается в 20 баллов.
- 1<=n<=100000,2<=p<=109. Оценивается в 40 баллов.
Примеры:
Вход 4 3 3 5 12 11Ответ
2Вход
3 5 1 2 7Ответ
1
Замечание
Число называется простым если оно делится только на себя и на единицу. (например: 2,3,5,7,11,13,17,…)
Запись a mod b обозначает взятие остатка от деления числа a на b.
- В первом тестовом примере подходят только 2 пары: (3,12),(5,11) так как (3+12) mod 3 = (3∗12) mod 3 и (5+11) mod 3 = (5∗11) mod 3
- {Во втором тестовом примере подходит только 1 пара: (2+7) mod 5 = (2∗7) mod 5}
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.