Задание 25: Программирование. Обработка целочисленных данных

1. Общая информация о задании

• Уровень сложности: высокий (Часть 2)
• Максимальный балл: 1
• Примерное время выполнения: около 20 минут
• Формат ответа: обычно таблица из 5 пар чисел — в первом столбце найденные числа, во втором — связанная величина (частное, сумма делителей, множитель…)

Суть: перебрать натуральные числа в заданном диапазоне и найти первые 5, удовлетворяющих условию. Ручной перебор невозможен — нужна программа на Python с оптимизацией цикла.

Задания: N25. Банк заданий | Учебник future-step

Материалы курса:

• Часть 1 — маски чисел, модуль fnmatch
• Часть 2 — делители, последние цифры
• Часть 3 — простые делители, произведение простых

2. Три типа заданий

На экзамене сначала определи тип, затем выбери шаблон. Ответ — первые 5 подходящих чисел в порядке возрастания.

3. Тип 1: маски чисел (fnmatch)

Когда: в условии дана маска — последовательность цифр с символами:

• ? — ровно одна произвольная цифра;
• * — любая последовательность цифр (в том числе пустая).

Число должно также делиться на заданное rem без остатка.

Подстановочные знаки

Шаблон решения

from fnmatch import fnmatch

mask = '3?12?14*5'          # маска из условия
rem = 1917                   # делитель из условия
start = 30120145             # минимальное число под маску (см. ниже)
limit = 10 ** 10             # верхняя граница из условия

for i in range(start + (-start % rem), limit, rem):
    if fnmatch(str(i), mask):
        print(i, i // rem)

Как найти start (нижнюю границу маски):

1. Удалить все *.
2. Вместо каждого ? поставить 0 (для минимального числа).

Пример: маска 33*21?7 → 332107; маска 4*4736*1 → 447361.

Оптимизация перебора:

• шаг цикла = rem (число из условия «делится на …»);
• старт: start + (-start % rem) — первое число ≥ start, кратное rem.

fnmatch проверяет всю строку целиком (как re.fullmatch). Число передаём через str(i).

Пример (задание 2520)

Маска 3?12?14*5, делитель 1917, числа ≤ 10¹⁰.

from fnmatch import fnmatch

for i in range(30120145 + (-30120145 % 1917), 10 ** 10, 1917):
    if fnmatch(str(i), '3?12?14*5'):
        print(i, i // 1917)

4. Тип 2: делители числа

Когда: нужно найти делители числа и проверить их свойства — сумму, минимум/максимум, окончание на цифру.

Эффективный поиск всех делителей

Делители идут парами: если i — делитель, то num // i — тоже. Достаточно перебрать i от 1 до √num.

from math import isqrt

def get_divisors(num):
    divisors = set()
    for i in range(1, isqrt(num) + 1):
        if num % i == 0:
            divisors |= {i, num // i}
    return divisors

Для числа 1 000 000: перебор до num — ~1 000 000 итераций; до isqrt(num) — ~1 000.

Последние цифры числа

Предпочтительнее % — быстрее, чем str(num)[-1].

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

Шаблон: сумма делителей R оканчивается на 6

from math import isqrt

def f(num):
    divisors = set()
    for i in range(1, isqrt(num) + 1):
        if num % i == 0:
            divisors |= {i, num // i}
    R = sum(divisors)
    if R % 10 == 6:
        return R
    return 0

cnt = 0
for i in range(500_001, 10 ** 20):
    if R := f(i):
        print(i, R)
        cnt += 1
        if cnt == 5:
            break

Оптимизация: нужны только min и max делители

Если условие касается только минимального и максимального делителя (не считая 1 и num), не собирай всё множество — достаточно первого найденного делителя i ≥ 2:

from math import isqrt

def f(num):
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            M = i + num // i
            if M % 10 == 4:
                return M
            return 0
    return 0

Шаблон: делитель, оканчивающийся на 11

from math import isqrt

def f(num):
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            if i % 100 == 11 and i != 11:
                return i
            j = num // i
            if j % 100 == 11 and j != 11:
                return j
    return 0

5. Тип 3: простые делители

Когда: среди делителей нужны простые числа; число — произведение ровно двух простых множителей; сумма min и max простых делителей.

Проверка простоты (алгоритм 6k±1)

from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    for div in range(5, isqrt(n) + 1, 6):
        if n % div == 0 or n % (div + 2) == 0:
            return False
    return True

Единица не простое число. Число 2 — единственное чётное простое.

Простые делители числа

def get_prime_divisors(num):
    return {d for d in get_divisors(num) if is_prime(d)}

Произведение ровно двух простых (полупростое число)

Перебираем делитель i от 2 до √num. Если num % i == 0, второй множитель j = num // i. Оба должны быть простыми.

from math import isqrt

def contains_digit(num, digit):
    return str(num).count(str(digit)) == 1

def f(num):
    for i in range(2, isqrt(num) + 1):
        if num % i == 0:
            j = num // i
            if contains_digit(i, 5) and contains_digit(j, 5):
                if is_prime(i) and is_prime(j):
                    return max(i, j)
    return 0

Порядок проверок: сначала быстрые (contains_digit), потом медленные (is_prime).

Сумма min и max простых делителей M

def f(num):
    divisors = [d for d in get_divisors(num) if is_prime(d)]
    if not divisors:
        return 0
    M = min(divisors) + max(divisors)
    if M > 60_000 and str(M) == str(M)[::-1]:  # палиндром
        return M
    return 0

6. Общий каркас программы

Почти все задачи 25 укладываются в одну схему:

cnt = 0
for i in range(START + 1, 10 ** 20):   # START — из условия «больше N»
    if result := check(i):              # функция проверки
        print(i, result)
        cnt += 1
        if cnt == 5:
            break

Оператор := (морж) удобен для присваивания внутри if:

if R := f(i):
    print(i, R)

7. Полезные операции

Модуль fnmatch — шпаргалка

from fnmatch import fnmatch, filter

fnmatch('30120145', '3?12?14*5')   # True / False
filter(['a1b', 'ab'], 'a?b')       # ['a1b']

8. Алгоритм решения на экзамене

1. Прочитать условие: диапазон, что искать, сколько чисел вывести
2. Определить тип (1 — маска, 2 — делители, 3 — простые)
3. Выписать формулу для второго столбца (R, M, частное, множитель…)
4. Написать функцию check(num) или цикл с fnmatch
5. Оптимизировать: шаг по делителю, нижняя граница маски, не искать лишние делители
6. Вывести 5 пар, проверить на маленьком примере вручную
7. Убрать отладочные print

9. Типичные ошибки

10. Краткий чек-лист

1. Какой тип? (маска / делители / простые)
2. Что писать во второй столбец?
3. С какого числа начинать перебор?
4. Можно ли ускорить цикл (шаг, isqrt, ранний выход)?
5. Написать код, вывести 5 пар
6. Проверить ответ

11. Источники

• Учебник ЕГЭ по информатике — future-step.ru
• Часть 1 — маски, fnmatch
• Часть 2 — делители
• Часть 3 — простые числа
• Банк заданий №25 — КЕГЭ