АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Соревнования
Новости Справка СДО
Регистрация  ||  Вход/выход
Забыли пароль?
Рейтинг авторов
 
О системе
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1928. Подготовка к ЕГЭ

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Одиннадцатиклассник Тимофей, прорешивая варианты ЕГЭ по информатике прошлых лет, наткнулся на следующую задачу. На вход программы поступает последовательность из N целых положительных чисел a1, a2, ..., aN. Необходимо определить количество таких пар индексов (i, j), что 1 ≤ i < j ≤ N и произведение ai × aj делится на заданное число S.

В варианте ЕГЭ, который прорешивал Тимофей, значение S было небольшой константой, заданной прямо в тексте условия. А сможете ли вы эффективно решить эту задачу для произвольного входного значения S?

Входные данные

В первой строке входных данных задаются два натуральных числа через пробел — количество чисел N и значение S. В каждой из последующих N строк записано одно натуральное число, не превышающее 109.

Выходные данные

Выведите одно целое число — искомое количество пар.

Система оценки

  • Подзадача 1 (50 баллов): 2 ≤ N ≤ 1000, 1 ≤ S ≤ 1000
  • Подзадача 2 (10 баллов): 2 ≤ N ≤ 105, 1 ≤ S ≤ 1000, S является простым числом
  • Подзадача 3 (10 баллов): 2 ≤ N ≤ 105, 1 ≤ S ≤ 1000, S является произведением двух различных простых чисел
  • Подзадача 4 (10 баллов): 2 ≤ N ≤ 105, 1 ≤ S ≤ 1000
  • Подзадача 5 (10 баллов): 2 ≤ N ≤ 105, 1 ≤ S ≤ 106
  • Подзадача 6 (10 баллов): 2 ≤ N ≤ 105, 1 ≤ S ≤ 109

Пример

Входные данные
4 26
2
6
13
2
Выходные данные
3

Примечание

В примере из условия существует всего шесть попарных произведений (a1·a2 = 2·6 = 12, a1·a3 = 2·13 = 26, a1·a4 = 2·2 = 4, a2·a3 = 6·13 = 78, a2·a4 = 6·2 = 12, a3·a4 = 13·2 = 26). Среди этих произведений три делятся на 26, поэтому ответ равен 3.

Жюри напоминает, что, решив много задач на частичные баллы, можно получить лучший результат, чем пытаясь решить одну задачу на полный балл

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований и сборов / Школьные олимпиады и курсы Вологодской области / ВсОШ, муниципальные этапы / Муниципальный этап 2018-2019 / Классы 9-11 /
1928. 1929. 2 - Числовая последовательность 1930. 3 - Согласные строки 1931. 4 - Инверсии
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.