Задание №25 — Проверка делимости
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задаватьи пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917. Количество строк в таблице для ответа избыточно.
Правильный ответ
351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905
Пояснение
Решение:
Перебирать все числа до не нужно: подходящие числа делятся на 1917, поэтому достаточно пройти по кратным — Их примерно в 1917 раз меньше.
Проверку маски удобно свести к регулярному выражению: символ «?» — это ровно один любой символ, то есть ., а символ «*» — любая (в том числе пустая) последовательность, то есть .*. Маска 3?12?14*5 превращается в шаблон 3.12.14.*5, и число подходит, если запись числа целиком совпадает с шаблоном.
Маска содержит два символа «?» (по одной произвольной цифре каждый) и одну «звёздочку», которая может раскрыться и в пустую строку — поэтому подходят числа разной длины, вплоть до .
import re
pattern = '3.12.14.*5'
d = 1917
k = d
while k <= 10 ** 10:
if re.fullmatch(pattern, str(k)):
print(k, k // d)
k += d
Программа выводит:
351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905Ответ: 351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905