АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
Forgot your password?
Authors ranklist
 
About project
Hello, Guest! Please login or register.

1928. Preparing to Exam

Time Limit: 1 seconds
Memory Limit:262144KB
Points:100
View Problem Statistics Submit Problem added 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.

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

View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests and Camps / School olympiads and couses of Vologda region / All-Russian school olympiad, municipal stage / Municipal stage 2018-2019 / Forms 9-11 /
1928. 1929. 2 - Numeric Sequence 1930. 3 - Consonant Strings 1931. 4 - Inversions
time generating 0.11 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.