@Sheephard

Как для каждого делителя из одного массива найти делители из другого массива с остатком 0?

Пишу код.
Мне для составления матрицы нужно условие, которое будет давать True в случае если элемент из списка а делится на очередной элемент из списка b нацело.
Сейчас у меня примитивный код с решением в лоб, но по времени он не проходит. Могу ли я как-то избавиться от списка в списке?
n = int(input())

lamps = [False]*n

for i in range(n):
    idk = i+1
    for j in range(len(lamps)):
        jd = j+1
        if jd%idk==0:
            lamps[j] = not lamps[j]


При n = 10000 (10^5) код не успевает из-за вложенного цикла. Как ускорить?
  • Вопрос задан
  • 84 просмотра
Решения вопроса 1
wataru
@wataru
Если я правильно понял задачу, то надо подсчитать для каждого i
sum_{j=1..n} (i%j?1:0) % 2.

Или - есть n ламп в ряд изначально не горящих. Переключаются каждая первая, каждая вторая, третья и т.д. Вопрос - а какие лампы горят в конце.

Разверните условие. Не переключайте каждую 1-ую, 2-ую и т.д. лампу, а подсчитайте для каждой лампы, сколько раз она будет переключена (потому что переключать их все по одной - это медленно. Надо как-то агрегировать вычисления)?

Лампа будет переключена ровно столько раз, сколько делителей у ее номера. Иными словами - вам надо понять, четное ли количество делителей у каждого числа. Вспоминаем, что любое число представимо в виде разложения на простые множители: p1^k1*p2^k2* ... pm^km. Можно подсчитать количество делителей - это будет (k1+1)(k2+1)...(km+1), ведь каждое простое число может входить в делитель в степени от 0 до ki включительно.

Теперь, в каком случае это число будет нечетным? Только если все ki четные. А это значит, что число - полный квадрат (все степени четные же. Берем корень, делим степени пополам, получаем целое число).

Итого ответ - проставить true в массиве по всем индексам i*i.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
deeplay Новосибирск
от 130 000 ₽
от 130 000 ₽
Enjoy PRO Санкт-Петербург
от 140 000 до 180 000 ₽
20 окт. 2020, в 22:57
5000 руб./за проект
20 окт. 2020, в 21:37
300000 руб./за проект
20 окт. 2020, в 21:18
500 руб./за проект