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

Question

[Sheephard]

Пишу код.
Мне для составления матрицы нужно условие, которое будет давать 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) код не успевает из-за вложенного цикла. Как ускорить?

Comments

[Anton Kuzmichev]

Есть тестовые входные и выходные данные? И более внятная формулировка задачи?

Answer 1

[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.