Задание 25. Информатика. ЕГЭ. Шастин. 18.12.2024

Просмотры: 491
Изменено: 1 февраля 2025

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

  1. символ «\(?\)» означает ровно одну произвольную цифру;
  2. символ «\(*\)» означает любую последовательность цифр произвольной длины; в том числе «\(*\)» может задавать и пустую последовательность.

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

Напишите программу, которая перебирает целые числа, большие \(500~000,\) в порядке возрастания и ищет среди них такие, у которых есть хотя бы один делитель, соответствующий маске \(2{*}3{?}.\) В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце - наименьший их делитель, соответствующий заданной маске.

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

Решение:

Python


from fnmatch import fnmatch

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

q = 0
n = 500_000
while q < 5:
    n += 1
    d = [x for x in divisors(n) if fnmatch(str(x), '2*3?')]
    if len(d):
        print(n, min(d))
        q += 1

Ответ:
\(500016 \,\, 20834\)
\(500018 \,\, 233\)
\(500020 \,\, 230\)
\(500038 \,\, 238\)
\(500040 \,\, 20835\)