Задание 25 ЕГЭ по информатике: маски чисел и делители — разбор и примеры

Задание 25 — программирование на обработку целых чисел. В нём два основных сюжета: числа, соответствующие маске (шаблону из цифр и специальных символов), и делители чисел (количество делителей, их сумма, наименьший или наибольший нетривиальный делитель). В обоих случаях ответ — таблица из нескольких строк: числа и связанные с ними значения. Главная трудность — уложиться во время: диапазоны большие, и программа должна перебирать не всё подряд, а только то, что нужно.

Что проверяет задание

• умение написать перебор с правильными границами и условиями;
• знание быстрых приёмов: перебор только кратных числа, поиск делителей до квадратного корня;
• работу с масками: символ ? означает ровно одну любую цифру, символ * — любую последовательность цифр, в том числе пустую;
• аккуратную запись ответа: строки в порядке возрастания чисел, значения через пробел.

Типичные формулировки

1. «Найдите все натуральные числа, не превышающие 10⁸, которые соответствуют маске 3?17*4 и делятся на 1993 без остатка. В ответе запишите числа в порядке возрастания, справа от каждого — результат деления на 1993».
2. «Найдите числа из отрезка [A; B], у которых ровно k натуральных делителей; для каждого выведите наибольший делитель, отличный от самого числа».
3. «Пусть M — сумма минимального и максимального натуральных делителей числа, не считая единицы и самого числа. Найдите первые пять чисел больше N, для которых M оканчивается на 7».
4. Числа, имеющие ровно три различных чётных делителя, простые числа особого вида и т. п.

Пошаговый метод

Для масок:

1. Определите, на что должно делиться число, и перебирайте только кратные: range(d, limit + 1, d). Это уменьшает перебор в d раз.
2. Каждое кратное переведите в строку и проверьте функцией fnmatch из стандартного модуля fnmatch — она понимает ? и * ровно в том смысле, что в задании.
3. Выводите число и частное.

Для делителей:

1. Делители ищите парами: если i делит n, то и n / i — делитель. Достаточно перебрать i от 1 до корня из n.
2. Храните делители в множестве, чтобы для точного квадрата корень не посчитался дважды.
3. Если нужны только нетривиальные делители (без 1 и n), уберите их из множества или начинайте перебор с 2.
4. Для каждого числа диапазона проверьте условие и выведите ответ.

Разбор примера 1 (маска)

Найдите все натуральные числа, не превышающие 10⁸, которые соответствуют маске 3?17*4 и делятся на 1993 без остатка. Для каждого числа укажите частное от деления на 1993.

Маска описывает числа, которые начинаются с цифры 3, затем идёт одна любая цифра, затем цифры 1 и 7, затем любое (возможно, пустое) количество цифр и в конце цифра 4. Перебирать все числа до 10⁸ долго, а кратных 1993 — всего около 50 тысяч. Программа находит пять чисел:

Проверим первое: 1993 · 15138 = 30 170 034, и запись 30170034 подходит под маску: 3, затем 0, затем 17, затем 003, затем 4.

Разбор примера 2 (делители)

Среди чисел отрезка [480 000; 480 200] найдите все числа, у которых ровно 40 натуральных делителей. Для каждого запишите само число и его наибольший делитель, отличный от самого числа.

Подходят три числа: 480 048, 480 080 и 480 144. Все они чётные, поэтому наибольший делитель, отличный от числа, — это половина числа (в общем случае — число, делённое на свой наименьший простой делитель).

Например, 480 080 = 2⁴ · 5 · 17 · 353, и количество делителей равно (4 + 1) · 2 · 2 · 2 = 40.

Код на Python

Пример 1 — маска и перебор кратных:

from fnmatch import fnmatch

for x in range(1993, 10**8 + 1, 1993):
    if fnmatch(str(x), '3?17*4'):
        print(x, x // 1993)

Пример 2 — делители до корня:

def divisors(n):
    d = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            d.add(i)
            d.add(n // i)
        i += 1
    return d

for n in range(480000, 480201):
    d = divisors(n)
    if len(d) == 40:
        print(n, max(d - {n}))

Для каждого числа цикл делает около 700 шагов (корень из 480 000), поэтому весь отрезок обрабатывается мгновенно. Если отрезок содержит миллионы чисел, ищите способ сократить перебор: например, числа с ровно тремя делителями — это квадраты простых чисел, и перебирать можно только простые.

Как проверить программу

Перед запуском на полном диапазоне проверьте функцию на числах, для которых ответ известен. Например, у числа 12 шесть делителей: 1, 2, 3, 4, 6, 12, а у числа 36 — девять (корень 6 должен посчитаться один раз). Для масок проверьте пару строк вручную: fnmatch('3517004', '3?17*4') должно вернуть True, а fnmatch('31704', '3?17*4') — False, потому что после тройки обязательно стоит ровно одна цифра перед 17. Если программа работает дольше минуты, остановите её и подумайте, как сократить перебор: шаг по кратным, границу по корню или предварительный отбор кандидатов.

Частые ошибки

• Перебор всех чисел до 10⁸ вместо кратных. Программа будет работать несколько минут.
• Неверное понимание *. Звёздочка допускает и пустую последовательность: маске 3?17*4 соответствует и шестизначное число 3x174.
• Делители до n, а не до корня. На больших числах это слишком медленно.
• Двойной учёт корня у точных квадратов. Используйте множество или отдельную проверку i * i == n.
• Путают «делители» и «нетривиальные делители». Внимательно читайте, считаются ли 1 и само число.
• Неправильный порядок строк в ответе. Числа записываются по возрастанию, значения — в той же строке через пробел.

Потренируйтесь

Решите задания № 25 в банке и задачи с проверкой кода, где программа должна уложиться в лимит времени. Подробнее о делителях и масках — в статье «Делители и маски чисел». Следующее задание — задание 26: сортировка и жадные алгоритмы.