values и число limit.
Два числа массива **связаны**, если их наименьшее общее кратное не больше limit. Связи переходят по цепочке: если a связано с b, а b с c, то a, b и c попадают в одну группу. Число, ни с кем не связанное, образует группу в одиночку.
Верните количество групп.
Проверять все пары — это O(n²) при n до 10⁵. Обратите внимание, что limit невелик.values=[3, 5, 6, 10, 25], limit=10 → 3
НОК(3, 6) = 6 и НОК(5, 10) = 10 — эти пары связаны. НОК(3, 5) = 15 и НОК(6, 10) = 30 больше 10, а 25 само по себе больше 10. Группы: {3, 6}, {5, 10}, {25}.
values=[1, 7, 20], limit=15 → 2
1 и 7 связаны (НОК = 7), а 20 больше 15 и остаётся одно.
values=[12], limit=5 → 1
Одно число — одна группа, даже если оно больше limit.
values различныvalues=[3, 5, 6, 10, 25], limit=10
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 89 тестов на сервере, включая скрытые.