Задача #1583

Делители и маски

Сложнее ЕГЭ

(С. Чайкин) Найдите пять наибольших натуральных чисел $N$ , не превышающих $10^{11}$ , которые являются антипростыми числами. В ответе перечислите найденные числа в порядке убывания, справа от каждого числа запишите число его делителей.

Примечание: Антипростое число - натуральное число, количество делителей которого больше чем у любого натурального числа меньше его.

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть

Ответ

97772875200

4032

80313433200

3840

73329656400

3600

64250746560

3584

48886437600

3456


from functools import *

def divs(x):
    k = set()
    for d in range(1, int(x**0.5)+1):
        if x % d == 0:
            k |= {d, x // d}
    return sorted(k - {1})[::-1]

# Все антипростые числа, не превышающие 10^11
# имеют не более 10^4 делителей, поэтому нам надо
# хранить не более 14 (~ 4log2(10)) простых чисел
p = [n for n in range(1, 50) if len(divs(n)) == 1]

# Сделаем функцию, которая будет находить минимальное натуральное число,
# у которого ровно k делителей. Из основной теоремы арифметики
# следует, что количество делителей равно (k1 + 1) * (k2 + 1) * ... * (km + 1),
# где k1, k2, ..., km - степени у простых чисел, входящих в разложение числа N.
# Очевидно, что ki является степенью простого числа, если K кратно (ki + 1).
# Поэтому будем перебирать все делители K и находить минимальное произведение
# простых чисел с найденными степенями.
# Для оптимизации перебора, будем использовать кэширование.

@cache
def f(k, i):
    if k == 1: return 1

    mn = 10 ** 50
    for d in divs(k):
        # если d является делителем, будем искать степень для
        # следующего простого числа
        mn = min(mn, p[i] ** (d - 1) * f(k // d, i + 1))
    
    return mn

# Мы точно не знаем, какое число будет антипростым, поэтому
# переберём все возможные значения K, для которых N не превышает
# 10^11, и отсортируем их в порядке возрастания N.
a = sorted((f(n, 0), n) for n in range(1, 10**4+1) if f(n, 0) <= 10 ** 11)

# При некоторых значениях K, N не будет являться антипростым числом
# поэтому сделаем список который будет хранить только антипростые числа.
b = [(0, 0)]

for x in a:
    # Мы точно знаем, что не пропускаем какое-то значение,
    # так как наш список отсортирован в порядке возрастания N.
    if b[-1][-1] < x[-1]:
        b += [x]

# Выводим 5 последних антипростых чисел
for n, k in b[-5:][::-1]:
    print(n, k)

Номер