n городов с номерами от 1 до n. Города x и y соединены дорогой напрямую, если у их номеров есть общий делитель, строго больший limit. Дороги двусторонние.
Для каждого запроса [a, b] из списка queries выясните, можно ли добраться из города a в город b — напрямую или через другие города.
Верните список из True и False: по одному значению на каждый запрос, в том же порядке.n=8, limit=2, queries=[[3, 6], [4, 8], [2, 3], [5, 7]] → [True, True, False, False]
3 и 6 делятся на 3, 4 и 8 — на 4: обе пары соединены дорогой напрямую. У 2 нет делителей больше 2, у 5 и 7 — только они сами, и других кратных до 8 нет, так что эти города изолированы.
n=12, limit=1, queries=[[3, 4], [5, 7]] → [True, False]
3 → 6 (общий 3) → 4 (общий 2): путь есть. 7 связан только с 14, а его в стране нет, поэтому 5 и 7 не связаны.
n=4, limit=0, queries=[[1, 4], [2, 3]] → [True, True]
При пороге 0 подходит делитель 1, а на него делится любое число: все города соединены между собой.
n=8, limit=2, queries=[[3, 6], [4, 8], [2, 3], [5, 7]]
[True, True, False, False]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 66 тестов на сервере, включая скрытые.