Question

Маской числа называется последовательность цифр, в которой могут встречаться символы:
- `?` — ровно одна произвольная цифра;
- `*` — любая последовательность цифр произвольной длины (включая пустую).

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

Найдите все натуральные числа, не превосходящие $10^9$, для которых выполнены все условия:
- соответствуют маске `*31*65?`;
- делятся на 31 и 2031 без остатка;
- количество делителей числа является степенью двойки.

В ответе запишите в первом столбце все найденные числа в порядке возрастания, справа от каждого — его частное от деления на 2031.

Accepted Answer

53831655 26505
333126651 164021
512313657 252247
647931651 319021
831966654 409634

Answer

Идея решения: перебрать все числа, кратные НОК(31, 2031), проверить соответствие маске, затем подсчитать делители и убедиться, что их количество — степень двойки.

Заметим, что оба делителя 31 и 2031 должны делить число нацело. Поскольку $2031 = 3 	imes 677$, а 31 — простое число, НОК$(31, 2031) = 31 	imes 2031 = 62961$. Перебираем числа с шагом 62961.

Для каждого кандидата:
1. Проверяем соответствие маске `*31*65?` с помощью функции `fnmatch`.
2. Подсчитываем все делители за $O(\sqrt{n})$: проходим от 1 до $\sqrt{n}$, и для каждого делителя $i$ добавляем как $i$, так и $n/i$.
3. Проверяем, является ли количество делителей степенью двойки (2, 4, 8, 16, ...).
4. Выводим число и его частное от деления на 2031.

```python
from fnmatch import fnmatch
import math

powers_of_two = set(2**i for i in range(1, 40))

for n in range(0, 10**9 + 1, 31 * 2031):
    if fnmatch(str(n), '*31*65?'):
        divisors = set()
        k = 1
        while k * k <= n:
            if n % k == 0:
                divisors.add(k)
                divisors.add(n // k)
            k += 1
        
        if len(divisors) in powers_of_two:
            print(n, n // 2031)
```

Сложность: $O\left(\frac{10^9}{62961} \cdot \sqrt{10^9}ight) \approx O(10^4)$ — приемлемо.

Задание №25ПрограммированиеЕГЭ по информатике