1. Введение

В задании 25 обычно встречаются два основных прототипа: задачи на маски и задачи на делители. Первый прототип связан с поиском чисел по шаблону записи. Второй — с анализом делителей числа, проверкой простоты и разложением на простые множители.

Главная идея обоих прототипов одна и та же: мы перебираем числа в нужном диапазоне и проверяем, выполняется ли условие задачи.

1

2. Теория по первому прототипу: маски

2.1. Что такое маска

Маска — это шаблон, по которому мы сравниваем запись числа. В условии обычно используются специальные символы:

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

Например, маска 1234?5 означает: число начинается с 12, далее может идти любая последовательность цифр, затем 34, одна произвольная цифра, цифра 5 и после неё снова может быть любая последовательность цифр.

1

2.2. Как маски работают в Python

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

1

2.3. Разбор кода по маскам

Условие задачи (Основная волна 2023)

Назовём маской числа последовательность цифр, в которой также могут встречаться символы ? и . Символ ? означает ровно одну произвольную цифру, а * — любую последовательность цифр произвольной длины, в том числе пустую. Среди натуральных чисел, не превышающих 10^8, найдите все числа, соответствующие маске 1234?5*, делящиеся на 2025 без остатка. В ответе нужно вывести найденные числа в порядке возрастания и соответствующие им результаты деления на 2025.

from fnmatch import fnmatch

for x in range(0, 10**8, 2025):
    if fnmatch(str(x), '12*34?5*'):
        print(x, x // 2025)
  • Импортируем fnmatch — функцию для проверки строк по маске.
  • Перебираем числа с шагом 2025, поэтому сразу рассматриваем только числа, кратные 2025.
  • str(x) переводит число в строку: fnmatch работает со строками.
  • fnmatch(str(x), '1234?5') проверяет соответствие записи числа маске.
  • Если число подходит, выводим само число и частное x // 2025.

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

3. Теория по второму прототипу: делители

3.1. Что такое делитель и как работает проверка делимости

Число d называется делителем числа x, если x % d == 0. В задачах этого типа почти всегда нужна отдельная функция, которая ищет делители числа.

  • делители удобно искать парами: d и x // d;
  • достаточно перебирать d только до √x;
  • после √x пары начинают повторяться, поэтому дальше идти не нужно.

3.2. Почему проверяют только до √x

Если у числа есть делитель больше √x, то ему обязательно соответствует парный делитель меньше √x. Поэтому все нужные пары мы уже найдём, если проверим делители от 2 до int(x**0.5) + 1.

1

3.3. Проверка простоты числа

Проверка простоты нужна в задачах, где условие говорит о простых делителях или простых множителях. Простое число больше 1 и имеет только два натуральных делителя: 1 и само себя.

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(n**0.5) + 1):
        if n % d == 0:
            return False
    return True
  • Если n < 2, число не является простым.
  • Перебираем возможные делители от 2 до √n.
  • Если нашли делитель, число составное.
  • Если делитель не найден, число простое.
1

3.4. Разложение числа на простые множители

В некоторых задачах недостаточно просто найти делители: нужно разложить число именно на простые множители. Для этого удобно использовать рекурсивную функцию M(x).

def M(x):
    for d in range(2, int(x ** 0.5) + 1):
        if x % d == 0:
            return [d] + M(x // d)
    return [x]
  • Ищем первый делитель d числа x.
  • Если нашли, добавляем d в список и продолжаем разложение числа x // d.
  • Если делитель не найден, значит x — простое число.
  • Результат функции — список простых множителей. Например, M(60) → [2, 2, 3, 5].
1

3.5. Разбор задачи №1: простые множители

Условие задачи (Основная волна 2026, день 1)

Напишите программу, которая перебирает целые числа, большие 2 626 695 891, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи 67 (67 — идущие подряд друг за другом в указанном порядке цифры 6 и 7). В ответе запишите первые 5 найденных чисел и для каждого — наименьший найденный множитель.

def M(x):
    for d in range(2, int(x ** 0.5) + 1):
        if x % d == 0:
            return [d] + M(x // d)
    return [x]

for x in range(2626695892, 2626795892):
    su = M(x)
    if len(su) == 2:
        if all(str(d).count('67') == 1 for d in su):
            print(x, min(su))
  • M(x) раскладывает число на простые множители.
  • su = M(x) сохраняет список простых множителей текущего числа.
  • len(su) == 2 проверяет, что число представлено произведением ровно двух простых множителей. Они могут совпадать, поэтому, например, p · p тоже подходит по этому признаку.
  • all(str(d).count('67') == 1 for d in su) проверяет каждый из двух множителей: сочетание цифр 67 должно встречаться в его записи ровно один раз.
  • min(su) — наименьший из найденных множителей, который требуется вывести вместе с числом.

3.6. Разбор задачи №2: базовые делители

Условие задачи

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

def d(x):
    dels = set()
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            dels.add(i)
            dels.add(x // i)
    return dels

for x in range(800000, 0, -1):
    dels = d(x)
    if len(dels) > 0:
        M = max(dels) - min(dels)
    else:
        M = 0
    if M % 23 == 0 and M != 0:
        print(x, M)
  • d(x) собирает все нетривиальные делители числа — без 1 и самого числа.
  • Ищем делители только до √x и сразу добавляем парный делитель x // i.
  • set() нужен, чтобы не получить повтор для полного квадрата, когда i == x // i.
  • Если делители есть, вычисляем M = max(dels) - min(dels).
  • Если нет нетривиальных делителей, M = 0.
  • Условие M % 23 == 0 and M != 0 учитывает отдельную оговорку задачи: ноль не считается кратным 23.
  • Цикл идёт с шагом -1, потому что числа нужно рассматривать в порядке убывания.

4. Практика

В этом разделе разберём пять задач. Здесь встречаются оба основных прототипа задания 25: работа с делителями и поиск чисел по маске.

4.1. Задача 1: соседние делители

Условие задачи

Напишите программу, которая перебирает целые числа, большие 2 250 000, в порядке возрастания и ищет среди них такие числа, в записи которых содержится ровно одна цифра 3 и у которых есть натуральный делитель D > 100, для которого число D + 1 также является делителем этого числа. В ответе запишите первые пять найденных чисел в порядке возрастания, а рядом — наименьший такой делитель D для каждого из них.

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

def D(x):
    dels = set()
    for d in range(1, int(x ** 0.5) + 1):
        if x % d == 0:
            dels.add(d)
            dels.add(x // d)
    return dels

k = 0
x = 2_250_000

while k < 5:
    x += 1

    if str(x).count('3') != 1:
        continue

    dels = D(x)
    good_d = [d for d in dels if d > 100 and x % (d + 1) == 0]

    if good_d:
        print(x, min(good_d))
        k += 1

Пояснение решения:

  1. Функция D(x) ищет делители парами: если d делит x, то x // d тоже является делителем. set() убирает возможные повторы у полных квадратов.
  2. Проверка str(x).count('3') != 1 сразу пропускает все числа, где цифра 3 встречается не ровно один раз.
  3. В списке good_d оставляем только делители d > 100, для которых d + 1 тоже делит x. Условие «d + 1 — делитель» записывается как x % (d + 1) == 0.
  4. Если подходящих делителей несколько, выводим min(good_d), потому что в ответе требуется наименьший D. Цикл останавливается после пяти найденных чисел.

Ответ:

2250360 140
2250378 117
2250936 612
2251530 269
2252316 452

4.2. Задача 2: три простых множителя и палиндром

Условие задачи

Напишите программу, которая перебирает целые числа, большие 12 345 678, в порядке возрастания и ищет среди них числа, удовлетворяющие условиям: число представлено в виде произведения ровно трёх простых множителей (не обязательно различных), а наибольший из этих трёх простых множителей является палиндромом. В ответе выведите первые 7 найденных чисел и соответствующий каждому из них наибольший простой множитель.

Главная сложность — получить именно простые множители с учётом повторений. Для этого удобно использовать рекурсивную функцию M(x).

def M(x):
    for d in range(2, int(x ** 0.5) + 1):
        if x % d == 0:
            return [d] + M(x // d)
    return [x]

k = 0
x = 12_345_678

while k < 7:
    x += 1
    m = M(x)

    if len(m) == 3:
        p = max(m)
        if str(p) == str(p)[::-1]:
            print(x, p)
            k += 1

Пояснение решения:

  1. M(x) раскладывает число на простые множители. Функция берёт первый найденный делитель и продолжает раскладывать оставшуюся часть числа.
  2. len(m) == 3 означает, что в разложении ровно три простых множителя. Повторы сохраняются, поэтому, например, p · p · q тоже считается произведением трёх множителей.
  3. max(m) выбирает наибольший простой множитель.
  4. Палиндром проверяем сравнением строки с её разворотом: str(p) == str(p)[::-1]. После каждого подходящего числа увеличиваем счётчик и останавливаемся на семи ответах.

Ответ:

12345913 757
12346077 17971
12346702 11411
12347243 787
12347386 32323
12347494 15551
12347537 383

4.3. Задача 3: сумма цифр делителя

Условие задачи

Найдите 5 наименьших чисел, больших 700 000, таких, что среди их нетривиальных делителей есть число, сумма цифр которого равна 13. Для каждого из 5 найденных чисел сначала выведите само число, затем — минимальный нетривиальный делитель, сумма цифр которого равна 13.

Нетривиальные делители — это все делители, кроме 1 и самого числа. После их поиска остаётся проверить сумму цифр каждого делителя.

def D(x):
    dels = set()
    for d in range(1, int(x ** 0.5) + 1):
        if x % d == 0:
            dels.add(d)
            dels.add(x // d)
    return dels

k = 0
x = 700_000

while k < 5:
    x += 1
    dels = D(x) - {1, x}

    s13 = [d for d in dels if sum(int(i) for i in str(d)) == 13]

    if s13:
        print(x, min(s13))
        k += 1

Пояснение решения:

  1. D(x) возвращает все натуральные делители числа, включая 1 и x.
  2. Выражение D(x) - {1, x} удаляет 1 и само число, поэтому остаются только нетривиальные делители.
  3. Для каждого делителя d переводим его в строку и складываем цифры: sum(int(i) for i in str(d)). Оставляем только те делители, у которых сумма равна 13.
  4. Если список s13 не пуст, число подходит. Из подходящих делителей выводим минимальный.

Ответ:

700002 58
700004 139
700005 2029
700010 350005
700011 193

4.4. Задача 4: маска и чётные делители

Условие задачи

Назовём маской числа последовательность цифр, в которой также могут встречаться символы ? и . Символ ? означает ровно одну произвольную цифру, а * — любую последовательность цифр произвольной длины, в том числе пустую. Среди натуральных чисел, больших 65000, найдите первые 7 чисел, удовлетворяющих маске 697*5? и имеющих не менее 4 чётных делителей. Запишите найденные числа в порядке возрастания, справа от каждого числа — сумму его чётных делителей.

Это комбинированная задача: сначала проверяем маску, а делители считаем только для тех чисел, которые уже подошли по записи. Так лишние числа не проходят дорогую проверку делителей.

from fnmatch import fnmatch

def D(x):
    dels = set()
    for d in range(1, int(x ** 0.5) + 1):
        if x % d == 0:
            dels.add(d)
            dels.add(x // d)
    return dels

k = 0
x = 65_000

while k < 7:
    x += 1

    if fnmatch(str(x), '6*97*5?'):
        even_dels = [d for d in D(x) if d % 2 == 0]

        if len(even_dels) >= 4:
            print(x, sum(even_dels))
            k += 1

Пояснение решения:

  1. fnmatch(str(x), '6975?') проверяет маску: число начинается с 6, затем может идти любая последовательность цифр, далее 97, снова любая последовательность, затем 5 и ровно одна произвольная цифра.
  2. Функцию D(x) вызываем только после проверки маски — это уменьшает количество лишних вычислений.
  3. В even_dels оставляем только чётные делители по условию d % 2 == 0.
  4. Если чётных делителей не меньше четырёх, выводим число и sum(even_dels). Перебор идёт по возрастанию, поэтому первые семь найденных чисел сразу являются ответом.

Ответ:

69750 129792
69752 122080
69756 139536
69758 75152
609750 1103232
609752 1291248
609754 630840

4.5. Задача 5: маска и кратность

Условие задачи

Назовём маской числа последовательность цифр, в которой также могут встречаться символы ? и . Символ ? означает ровно одну произвольную цифру, а * — любую последовательность цифр произвольной длины, в том числе пустую. Среди натуральных чисел, не превышающих 10^10, найдите все числа, соответствующие маске 9?9798, делящиеся на 50068 без остатка и содержащие хотя бы одну цифру 0. В ответе запишите найденные числа в порядке возрастания, а рядом — результаты деления этих чисел на 50068.

Здесь не нужно перебирать все числа до 10^10. Раз число обязано делиться на 50068, сразу перебираем только кратные 50068 — это сокращает перебор в десятки тысяч раз.

from fnmatch import fnmatch

for x in range(50068, 10**10, 50068):
    if fnmatch(str(x), '9?979*8') and str(x).count('0') > 0:
        print(x, x // 50068)

Пояснение решения:

  1. Шаг цикла равен 50068, поэтому каждое перебираемое число уже гарантированно делится на 50068. Отдельная проверка x % 50068 == 0 не нужна.
  2. Маску 9?979*8 проверяем через fnmatch. Символ ? занимает ровно одну цифру, а * — произвольное количество цифр, включая ноль цифр.
  3. str(x).count('0') > 0 проверяет, что в записи числа есть хотя бы один ноль.
  4. Второй столбец ответа — частное x // 50068. Так как цикл идёт по возрастанию, ответы сразу выводятся в нужном порядке.

Ответ:

9097906348 181711
9297928008 185706

Видео разбор