Задание 25

Пример 1

Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 800000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.

Например, для числа 20 М = 2 + 10 = 12.

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

Ответ:

Пример 2

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
 – символ «?» означает ровно одну произвольную цифру;
 – символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917.
Количество строк в таблице для ответа избыточно.

Ответ:

Теория

Данное задание проверяет умение создавать собственные программы (10–20 строк) для обработки целочисленной информации. Поиск данных, удовлетворяющих определенным критериям. Нахождение минимального или максимального значение и работа с циклами. В ответе необходимо указать большое количество чисел - самое сложное в задаче (упражнение на правильность перенесения в бланк 😉).

Решение

Пример 1

В цикле проверяем все числа от 800001 и больше, пока не будет найдено 5 чисел. Для поиска минимального делителя числа перебираем все делители от 2 до квадратного корня из числа (можно и до числа//2+1 - оптимальность алгоритма перебора делителей проверять не будут). Если минимальный делитель >2 найден, то максимальный делитель равен число//минимальный делитель. Суммируем минимальный и максимальный делители и проверяем на кратность 4.

Результат работы программы

Пример 2

Символ «?» означает ровно одну произвольную цифру - от 0 до 9, а символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Алгоритм "в лоб" сделать цикл по символам ? - вложенный по знаку «*» (сначала  - 0 цифр, потом 1 цифра и наконец 2 цифры). Проанализировав заданную маску 3?12?14*5 легко увидеть что знак «*» максимально 2 цифры, т.е. 0≤*≤2 символов. Далее преобразуем строку в число и проверяем делимость.

Результат работы программы

Ответ

Пример 1:  (Время не более 20 минут)

Пример 2:  (Время не более 20 минут)