25 задание ЕГЭ информатика

Обработка целых чисел: делители и маски

1 балл ≈ 20 мин уровень В Программа обработки целых чисел (делители, маски)

Задание 25 – перебор чисел в диапазоне: найти числа с заданными свойствами делителей (количество, сумма, простые делители) или соответствующие маске (? – одна цифра, * – любая последовательность цифр) и делящиеся на заданное число. Ответ – таблица чисел и значений. 1 балл.

Делители за O(√n)

def divs(n):
    d = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            d.add(i)
            d.add(n // i)
    return sorted(d)        # делители без 1 и самого числа

print(divs(20))             # [2, 4, 5, 10]
res = []
n = 800000
while len(res) < 5:
    n += 1
    d = divs(n)
    m = d[0] + d[-1] if d else 0
    if m % 10 == 4:
        res.append((n, m))
for x in res:
    print(*x)

Маски – модуль fnmatch

from fnmatch import fnmatch

for n in range(2023, 10**8 + 1, 2023):     # сразу шагаем по кратным
    if fnmatch(str(n), "1?2*7"):
        print(n, n // 2023)

Маска «1?2*7»: первая цифра 1, затем любая одна, затем 2, затем любое количество цифр (в том числе ноль), последняя – 7.

Разобранный пример. Для 20 делители без 1 и самого числа: 2, 4, 5, 10; M = 2 + 10 = 12. Для простого числа делителей нет – M = 0. Для 18207 маска «1?2*7» подходит: 1-8-2-«0»-7, и 18207 = 2023 · 9.

Ловушки: делитель √n добавляется один раз – множество set это решает; перебор делителей до n (а не до √n) не уложится во время; «первые пять чисел» – останавливай цикл; звёздочка может означать и пустую последовательность.

На экзамене

Делители – только до корня, парный делитель n // i добавляй сразу.
Для «кратно k и подходит под маску» шагай range(k, предел, k) – в тысячи раз быстрее.
Простые числа: len(divs(n)) == 0 при n > 1.

Разобранные задания 25 из открытого банка ФИПИ

Пример 1 · код ФИПИ 53B650

Напишите программу, которая перебирает целые числа, большие 1 481 011, в порядке возрастания и ищет среди них представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 7.

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

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

Показать ответ и решение

Ответ: 1481023 87119 1481057 87121 1481089 1217 1481171 18749 1481179 211597

Перебираем числа подряд, раскладываем на простые множители; подходят числа вида $p \cdot q$ (p, q – простые), где у каждого множителя ровно одна цифра 7.

Во втором столбце – наибольший множитель.

Пример 2 · код ФИПИ 57cFD7

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

$-$ символ «?» означает ровно одну произвольную цифру;

$-$ символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать
и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 89*6?7?9?, делящиеся на 9874 без остатка.

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

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

Показать ответ и решение

Ответ: 8901677598 901527 8905627198 901927 8912617990 902635 8941667298 905577 8952607690 906685 8970607992 908508 8988647790 910335

Раскрываем маску 89*6?7?9? (вместо «*» – строки цифр нужной длины, общая длина не больше 10), проверяем делимость на 9874.

Найдено 7 чисел, рядом – частные.

Пример 3 · код ФИПИ 703256

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

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

Показать ответ и решение

Ответ: 500002 89 500003 71429 500004 19 500007 166669 500013 18519

Для каждого числа > 500000 перебираем делители до $\sqrt{n}$ (с парными), отбираем оканчивающиеся на 9, кроме 9 и самого числа, берём наименьший.

Первые пять: 500002 (89), 500003 (71429), 500004 (19), 500007 (166669), 500013 (18519).

Частые вопросы о задании 25

Сколько баллов даёт задание 25 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 20 мин. Уровень сложности – В.

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

Как подготовиться к заданию 25?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.