DjangoBB LoFi version

Полная версия: Задача №635. Дружественные числа

Начало » Центр помощи » Задача №635. Дружественные числа

Fiares_Curie

Окт. 28, 2021 14:39:21

Два различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа, а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от M до N.

Входные данные
В первой строке находятся числа M и N. 1 <= M <= N <= 1 000 000, все числа целые.

Выходные данные
В каждой строке вывести по паре чисел через пробел. Первое число пары должно быть меньше второго. Строки должны быть отсортированы в порядке возрастания первого числа пары. Если пар дружественных чисел в промежутке нет, вывести “Absent”.

 def sd(k):
    s = 0
    m = int(k**0.5)
    for i in range(1, m+1):
        if k%i == 0:
            if i**2 == k:
                s += i    
            else:
                s+=i
                s+=(k//i)
    s -= k
    return s
a = input().split()
n,m = int(a[0]), int(a[1])
f = 0
for i in range(n, m):
    for j in range(i+1, m+1):
        if sd(i) == j and sd(j) == i:
            print(i, j)
            f = 1
if f == 0:
    print('Absend')

Программа не заходит в системе на одном из тестов по времени. Что не так?

FishHook

Ноя. 1, 2021 14:39:04

Fiares_Curie
Очевидно, ваш алгоритм не оптимален. Вообще, мне кажется, что вы решаете задачу “в лоб”, ровно как написано. Вы для каждого i перебираете диапазон и проверяете условие(i, j) то есть ваш алгоритм имеет квадратичную сложность (для n значений вам надо выполнить n**2 вычислений). Я бы делал не так, вы можете для каждого i из диапазона не искать соответсвующие дружественные числа в том же диапазоне, а вычислить все его дружественные числа и отсеять те из них, которые попадают в диапазон.

py.user.next

Ноя. 2, 2021 23:03:52

Fiares_Curie
Программа не заходит в системе на одном из тестов по времени. Что не так?

Я думаю, эта задача разбиралась 100500 раз на разных языках и ты бы просто мог в Интернете найти её 100500 решений и выбрать оптимальное, а заодно и узнать, как это делать в общем с целым классом подобных задач.

Похоже, надо брать разные наборы делителей, умножать и суммировать их, отыскивая сходства в получающихся числах. Тогда не нужно перебирать диапазон весь, раскладывая на множители каждое число, которое с большой вероятностью не подходит под искомое.