Loading [MathJax]/jax/output/SVG/jax.js

4-й этап Республиканской олимпиады по информатике 2019, 9 класс, Актобе


Задача A. Найдите все пары

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Дано простое P, натуральное n и массив a размера n. Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на P что и сумма. Более формально, если выполняется условие xy mod P=(x+y) mod P то пара (x,y) считается хорошей. Найдите количество хороших пар в массиве.
Формат входного файла
В первой строке входного файла заданы два целых числа n (1<=n<=105) — количество чисел в массиве, P (2<=P<=109) — заданное простое число P. Во второй строке входного файла заданы n чисел ai (0<=ai<=109) - i-число в массиве.
Формат выходного файла
Выведите одно целое число - количество хороших пар в массиве.
Система оценки
Данная задача содержит четыре подзадачи:
  1. 1<=n<=1000,2<=p<=1000. Оценивается в 20 баллов.
  2. 1<=n<=1000,p=2. Оценивается в 20 баллов.
  3. 1<=n<=100000,2<=p<=1000. Оценивается в 20 баллов.
  4. 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. ( Nurdaulet Akhanov )
посмотреть в олимпиаде

Комментарий/решение:

  -3
5 года 3 месяца назад #

показать/скрыть код

C++

пред. Правка 2   0
4 года назад #

[deleted.]

пред. Правка 2   0
4 года назад #

[deleted.]

пред. Правка 2   1
5 года 2 месяца назад #

  0
4 года 10 месяца назад #

показать/скрыть код

C++

  1
4 года назад #

показать/скрыть код

C++

  1
3 года 11 месяца назад #

показать/скрыть код

C++

AC

  1
1 года 5 месяца назад #

показать/скрыть код

C++