|
Задачка из ЕГЭ
(Время: 3 сек. Память: 256 Мб Сложность: 53%)
Задан массив целых чисел A[1..N], состоящий из N элементов.
Требуется определить количество таких троек чисел в массиве, чтобы расстояние между любой парой чисел из тройки было не менее K, а произведение всех трёх чисел было кратно натуральному числу M.
Расстояние между элементами массива Ai и Aj равно значению |i-j|.
Входные данные
Первая строка входного файла INPUT.TXT содержит три целых числа: N, K и M (1 ≤ N, K, M ≤ 106). При этом гарантируется, что число M представляет собой произведение двух простых чисел.
Вторая строка входных данных содержит элементы массива Ai – целые числа, не превышающие 107 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 2 10
24 13 25 60 88 3 | 4 |
Пояснение к примеру
В исходном массиве можно выделить 4 тройки, удовлетворяющие условию задачи: (24, 25, 88), (24, 25, 3), (24, 60, 3) и (13, 60, 3).
Система оценки
Решения, работающие только для N ≤ 100, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
