ЕГЭ Информатика 25 (2025): Решение задачи о делителях

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

Задача 1: Минимальный и максимальный делители

Условие: Пусть M — сумма минимального и максимального натуральных делителей целого числа (не считая единицы и самого числа). Если таких делителей нет, M = 0. Напишите программу, которая перебирает целые числа больше 800 000 в порядке возрастания и находит среди них такие, для которых M оканчивается на четвёрку. В ответе запишите первые пять найденных чисел и соответствующие им значения M.

Решение:

Программа перебирает числа, начиная с 800 001. Для хранения количества найденных чисел используется переменная K. Для каждого числа I ищется множество делителей divs. Перебор делителей ведётся от 2 до квадратного корня из I, так как если d — делитель, то I/d — тоже делитель.

import math

A = 800001
K = 0
while K < 5:
    divs = set()
    for d in range(2, int(math.sqrt(A)) + 1):
        if A % d == 0:
            divs.add(d)
            divs.add(A // d)
    if len(divs) > 0:
        M = min(divs) + max(divs)
        if M % 10 == 4:
            print(A, M)
            K += 1
    A += 1

Код инициализирует переменную A значением 800001. Цикл while продолжается до нахождения 5 чисел, удовлетворяющих условию. Вложенный цикл for перебирает числа от 2 до квадратного корня из A. Если число является делителем, оно добавляется в множество divs. Если множество не пусто, вычисляется сумма минимального и максимального делителей (M), и проверяется, оканчивается ли M на 4. Если да, то выводится число A и значение M.

Задача 2: Маска и делимость

Условие: Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, которые соответствуют маске 3??1?1?5 и делятся на 1917 без остатка.

Решение:

Программа перебирает числа, кратные 1917, начиная с нуля, с шагом 1917, и проверяет соответствие маске 3??1?1?5.

import fnmatch

for x in range(0, 10**10, 1917):
    if fnmatch.fnmatch(str(x), '3??1?1?5'):
        print(x, x // 1917)

Код перебирает числа, кратные 1917, с шагом 1917, от 0 до 10¹⁰. Для каждого числа проверяется соответствие маске ‘3??1?1?5’ с помощью функции fnmatch.fnmatch. Если число соответствует маске, оно выводится вместе с результатом деления на 1917.

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