Ctrl K

Пары с кратным произведением

Сложная
Дан массив положительных целых чисел values и число divisor. Посчитайте количество пар индексов i < j, для которых произведение values[i] · values[j] делится на divisor без остатка. Перебор всех пар здесь слишком медленный — подумайте, что на самом деле важно в каждом числе.
Пример 1
values=[3, 4, 6, 9], divisor=6 → 5

Произведения пар: 3·4 = 12, 3·6 = 18, 3·9 = 27, 4·6 = 24, 4·9 = 36, 6·9 = 54. На 6 не делится только 27, поэтому ответ 5.

Пример 2
values=[5, 7, 11], divisor=3 → 0

Ни одно число не делится на 3, значит, и ни одно произведение тоже.

Пример 3
values=[2, 2], divisor=4 → 1

Каждое число по отдельности на 4 не делится, а их произведение 4 — делится.

Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁵
  • 1 ≤ divisor ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамая большая группа с общими делителями СложнаяСобрать единицу СложнаяГорода, связанные большими делителями СложнаяБлижайший взаимно простой предок СложнаяРазличные НОД наборов Сложная
загружаем Python…
Вход
values=[3, 4, 6, 9], divisor=6
Ожидается
5

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 104 теста на сервере, включая скрытые.