Задача CSES Counting Divisors

Question

Задача с сайта CSES Задачу решаю верно, но при проведении некоторых тестов пишет, что время выполнения превышено. Как можно оптимизировать код?

divs = 0
divs_count = []
div_list = []
n = int(input())
i = 0
while n > i and 10*n**6 >= n >= 1:
  x = int(input())
  if 10*x**6 >= x >= 1:
    div_list.append(x)
  i += 1
g = 0
while g < len(div_list): 
    i = div_list[g]
    divs = 0
    while i > 0:
        if div_list[g] % i == 0:
            divs += 1
        i -= 1
    divs_count.append(str(divs))
    g += 1

print('\n'.join(divs_count))

Ildar · Answer 1 · 2020-06-30T20:37:14.243

1

наивное решение O(sqrt(n)):

def count_divisors(num):
    divisors = set()
    square = num ** 0.5
    for divisor in range(1, int(square) + 1):
        if num % divisor == 0:
            divisors.add(divisor)
            divisors.add(num // divisor)
return len(divisors)


def main():
    n = int(input('n: '))
    for i in range(n):
        num = int(input('num: '))
        print(count_divisors(num))
if name == 'main':
    main()

Update:

для быстрого решения есть ответ здесь: https://ru.stackoverflow.com/questions/562346/Количество-делителей-числа

edited Jun 30 '20 at 20:37

answered Jun 30 '20 at 15:52

Ildar

2,802

У вас тоже решение правильное, но по времени выполнения не проходит некоторые тесты. Выдает TIME LIMIT EXCEEDED – CyberGenius Jun 30 '20 at 19:16
@CyberGenius исправил – Ildar Jun 30 '20 at 20:39
@Ildar, Здравствуйте! На сайте CSES я пробовал Ваше и моё решение, но почему-то они оба не проходят по времени, хотя наши решения теоретически верные. Я решал такое же задание на платформе Сириус, и там моё точно такое же решение прошло по времени (скорее всего, там тоже была 1 секунда). Мне кажется, проблема не в нашем решении, а в их сайте… – Daniil Savinov Jun 30 '20 at 20:59
1

@DaniilSavinov здравствуйте, есть более быстрое решение с лучшей асимптотикой которое описано в ссылке пониже – Ildar Jul 01 '20 at 06:56
@Ildar, спасибо, теперь понял! Что-то забыл, что можно воспользоваться разложением числа :) – Daniil Savinov Jul 01 '20 at 08:50

Daniil Savinov · Answer 2 · 2020-07-01T09:18:03.333

Код решения задачи:

# если число разложить в виде произведения простых чисел (например, 24 = 2^3 * 3),то количеством делителей будет произведение всех степеней, увеличенных на 1. В данном случае кол-вом делителей числа 24 будет (3 + 1) * (1 + 1) = 4 * 2 = 8.
def count_of_divisors(n):
    a = []
    d_counter = 0
    mult = 1
    d = 2   # начальный делитель - 2 (т.к. самое маленькое простое число - 2)
    while d * d <= n:   # пока d <= √n
        while n % d == 0:   # пока n делится на d
            n //= d     # делим n на делитель
            d_counter += 1  # инкрементируем степень (количество) делителя
        mult = d_counter + 1
        d_counter = 0   # обнуляем цикл по окончании вложенного цикла
        d += 1  # инкрементируем делитель
    if n > 1: # если n ещё не равно 1, то n - простое, и оно делится только на себя (и на 1)
        mult = 2
    return mult

Задача CSES Counting Divisors

2 Answers2