5C8ABE — Делители, маски и отбор чисел: ответ и решение

Впишите правильный ответ.

Пусть R – сумма различных натуральных делителей целого числа, не считая единицы и самого числа.

Напишите программу, которая перебирает целые числа, бо́льшие 500 000, в порядке возрастания и ищет среди них такие, для которых R оканчивается на цифру 9.

В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения R.

Например, для числа 20 R = 2 + 4 + 5 + 10 = 21.

Количество строк в таблице для ответа избыточно.

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

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

3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена»

3.5 Многоразрядные целые числа, задачи длинной арифметики

Тип ответа:

Краткий ответ

Номер: 5C8ABE

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINF5C8ABE

Ответ: (500014; 250009), (500038; 495289), (500040; 1170359), (500054; 250029), (500058; 667289)

Решение.
Требуются первые пять чисел, строго больших 500000. Начинаем с 500001 и рассматриваем целые n подряд в порядке возрастания.
Для каждого целого d от 2 до ⌊√n⌋ проверяем остаток при делении n на d. При нулевом остатке добавляем d и парный делитель nd. Множество устраняет повторение в случае d² = n.
Это полный список делителей без 1 и n: в любой паре сомножителей хотя бы один не больше √n. Поэтому каждую пару находим, в том числе пары с большим вторым делителем.
В сумму R входят только различные делители без 1 и n. Каждый элемент найденного множества учитываем ровно один раз.
Проверяем, что остаток от деления R на 10 равен 9.
n = 500014.
R = 2 + 250007 = 250009.
250009 = 10 · 25000 + 9.
n = 500038.
R = 2 + 7 + 11 + 14 + 17 + 22 + 34 + 77 + 119 + 154 + 187 + 191 + 238 + 374 + 382 + 1309 + 1337 + 2101 + 2618 + 2674 + 3247 + 4202 + 6494 + 14707 + 22729 + 29414 + 35717 + 45458 + 71434 + 250019 = 495289.
495289 = 10 · 49528 + 9.
n = 500040.
R = 2 + 3 + 4 + 5 + 6 + 8 + 9 + 10 + 12 + 15 + 18 + 20 + 24 + 27 + 30 + 36 + 40 + 45 + 54 + 60 + 72 + 90 + 108 + 120 + 135 + 180 + 216 + 270 + 360 + 463 + 540 + 926 + 1080 + 1389 + 1852 + 2315 + 2778 + 3704 + 4167 + 4630 + 5556 + 6945 + 8334 + 9260 + 11112 + 12501 + 13890 + 16668 + 18520 + 20835 + 25002 + 27780 + 33336 + 41670 + 50004 + 55560 + 62505 + 83340 + 100008 + 125010 + 166680 + 250020 = 1170359.
1170359 = 10 · 117035 + 9.
n = 500054.
R = 2 + 250027 = 250029.
250029 = 10 · 25002 + 9.
n = 500058.
R = 2 + 3 + 6 + 9 + 13 + 18 + 26 + 39 + 78 + 117 + 234 + 2137 + 4274 + 6411 + 12822 + 19233 + 27781 + 38466 + 55562 + 83343 + 166686 + 250029 = 667289.
667289 = 10 · 66728 + 9.
Полный последовательный перебор от 500001 до 500058 включительно проверяет 58 чисел. Условие выполняется ровно для пяти перечисленных n. Все меньшие допустимые кандидаты проверены, поэтому это именно первые пять чисел.
Проверка результата.
Воспроизводимая программа Python:

from math import isqrt

def proper_divisors(n):
    result = set()
    for d in range(2, isqrt(n) + 1):
        q, r = divmod(n, d)
        if r == 0:
            result.update((d, q))
    return sorted(result)

n = 500000
found = 0
while found != 5:
    n += 1
    d = proper_divisors(n)
    value = sum(d)
    ok = value % 10 == 9
    if ok:
        print(n, value)
        found += 1

Результат: в каждой строке слева n, справа R.
500014 — 250009
500038 — 495289
500040 — 1170359
500054 — 250029
500058 — 667289
Ответ: (500014; 250009), (500038; 495289), (500040; 1170359), (500054; 250029), (500058; 667289).

Задание EGEINF5C8ABE: Делители, маски и отбор чисел

Решение задания EGEINF5C8ABE

Помочь улучшить сайт

Комментарии к решению