Условие: № 7724 (Уровень: Базовый)
• Статья подготовлена командой itpy, подписывайтесь на наш телеграм канал!
(Грачев Н.) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
- символ «?» означает ровно одну произвольную цифру;
- символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Найдите все натуральные числа, не превосходящие 109, для которых выполнены все условия:
- соответствуют маске *18??18;
- делятся на 18 и на 1018 без остатка;
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, справа от каждого числа кол-во его делителей.
from fnmatch import *
for x in range(1018, 10**9, 1018):
if fnmatch(str(x), '*18??18'):
if x % 18 == 0:
divisors = set()
for j in range(1, int(x**0.5)+1):
if x % j == 0:
divisors.add(j)
divisors.add(x // j)
print(x, len(divisors))
Комментарии к решению:
- from fnmatch import * - импортируем все функции из библиотеки fnmatch, который предоставляет возможность сравнивать строки с шаблонами.
- for x in range(1018, 10**9, 1018): - начинаем цикл, перебирая значения x в диапазоне от 1018 до 10**9 с шагом 1018 (таким образом мы сразу ищем числа, которые делятся на 1018 без остатка см. условие).
- if fnmatch(str(x), '*18??18'): - проверяем, если строковое представление x соответствует шаблону '*18??18' с помощью функции fnmatch.
- if x % 18 == 0: - проверяем, если x делится на 18 без остатка.
- divisors = set() - создаем пустое множество для хранения делителей.
- for j in range(1, int(x**0.5)+1): - начинаем цикл, перебирая значения j от 1 до корня из x плюс 1 (int(x**0.5)+1 помогает нам искать пары чисел, используя корни чисел, так же это оптимизирует работу алгоритма).
- if x % j == 0: - проверяем, если x делится на j без остатка.
- divisors.add(j) - добавляем j в множество делителей.
- divisors.add(x // j) - добавляем результат целочисленного деления x на j в множество делителей.
- print(x, len(divisors)) - выводим значение x и количество делителей в множестве.
