Задание 25. Обработка целых чисел

Условие варианта демонстрационной работы.

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

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

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

Среди натуральных чисел, не превышающих $10^{10}$, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1917.

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

from fnmatch import fnmatch

fnmatch('123', '1*')     # True: «*» забирает всё, что осталось
fnmatch('123', '?*3')    # True: «?» ушла под 1, «*» под 2
fnmatch('123', '?*2')    # False: последний символ обязан быть 2

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

1. «В лоб» не подходит. range(1, 10**10 + 1) и проверка каждого числа – это $10^{10}$ итераций. На обычном компьютере такой перебор идёт около двух часов: программа формально верна, но ответа вы не дождётесь.
2. Шаг равен делителю. Нас интересуют только числа, делящиеся на 1917, а их в диапазоне 10**10 // 1917 = 5 216 484. Идём по ним шагом D, а не по всем подряд, – и вместо десяти миллиардов проверок остаётся пять миллионов, то есть секунды. Этой ступени уже достаточно, чтобы решить задачу на экзамене.
3. Границы маски сужают диапазон. Из самой маски видно, между какими числами она вообще может сработать. Наименьшее подходящее – заменить ? нулями, а * выбросить: 30120145. Наибольшее – заменить ? девятками, а * двумя девятками: в маске без звёздочки 8 цифр, 8 + 2 = 10 – столько цифр у чисел до $10^{10}$, а третья девятка дала бы уже 11 цифр и число больше $10^{10}$; выходит 3912914995. Первое кратное 1917, не меньшее нижней границы, – это (low + D - 1) // D * D = 30121821: прибавили D - 1 и округлили вниз, потом умножили на D, тем самым округлили вверх до кратного. Проверок остаётся 2 025 453.

Ступень номер два обязательна: она сокращает перебор почти в две тысячи раз (1917 – это как раз шаг), и на экзамене без неё делать нечего. Третья – приятный бонус, который срезает время ещё вдвое: на экзамене нормально всё, что досчитывается быстрее секунд тридцати. Если считать границы некогда, range(D, 10**10 + 1, D) тоже даёт верный ответ.

Условие из демонстрационной работы 2027.

Напишите программу, которая перебирает целые числа, бо́льшие 1 103 285 717, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи 16 (16 – идущие подряд друг за другом в указанном порядке цифры 1 и 6).

В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце – для каждого из них соответствующий наименьший найденный множитель.

Сначала переведём условие на человеческий язык: ищем числа $n = p \cdot q$, где $p \le q$ – оба простые, и в записи каждого ровно одно «16». Печатаем само n и его наименьший множитель p – именно он идёт во второй столбец. Оговорка «не обязательно различных» разрешает $p = q$: полный квадрат простого тоже подходит.

1. Прямой путь – разложить каждое $n$. Функция prime_factors из блока «Заготовки» ниже раскладывает число на простые множители, остаётся проверить, что их ровно два и оба «хорошие». До пятого ответа надо перебрать 42 830 чисел, и на каждом простом $n$ – а простые среди них составляют примерно каждое двадцатое – деление идёт до самого корня, около 33 тысяч шагов. В сумме секунд десять – двенадцать. Для экзамена это уже годится: ответ получен, дальше – ускорение ради удобства.
2. Выход на первом делителе. Полное разложение не нужно: первый найденный делитель $n$ – это и есть наименьший множитель p, и он заведомо простой (будь он составным, раньше нашёлся бы его собственный делитель). Проверили p и частное $q = n / p$ – и break, дальше делить незачем. Около пяти секунд: делений на простых $n$ по-прежнему много, зато на всех остальных цикл обрывается сразу.
3. Делить только на подходящие p. Меньший из двух множителей не больше $\sqrt{n}$, а корень из наших чисел – около 33 216. Значит, p – одно из простых чисел до этой границы, в записи которых ровно одно «16». Таких всего 179 (из 4203 простых до 40000) – выписываем их один раз заранее в список small и делим $n$ только на них. Как только p нашлось, проверяем q и выходим: если $n = p \cdot q$ из двух простых, других простых делителей до корня у него нет. А проверка p * p > n обрывает перебор списка, когда кандидаты кончились. Меньше секунды.

Пригодны все три ступени: на экзамене нормально всё, что досчитывается быстрее секунд тридцати. Если список не приходит в голову, вторая ступень – это пять строк:

for p in range(2, isqrt(n) + 1):
    if n % p == 0:          # первый делитель – наименьший, он простой
        q = n // p
        if good(p) and good(q) and is_prime(q):
            print(n, p)
            found += 1
        break

В решении ниже – третья ступень: код не сложнее, одна строка со списком small, а считается в семь раз быстрее.

Граница 40000 взята с запасом – она больше корня из любого проверяемого числа, так что ни один кандидат в p не потеряется. Лишние элементы списка отсекает не она, а p * p > n: как только кандидат перевалил за корень из текущего $n$, дальше пробовать нечего.

Три функции, которые нужны почти в любой задаче 25. Надо уметь написать их по памяти.

from math import isqrt

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for d in range(3, isqrt(n) + 1, 2):   # только нечётные до корня
        if n % d == 0:
            return False
    return True

def divisors(n):
    ds = set()                            
    for d in range(1, isqrt(n) + 1):
        if n % d == 0:
            ds.add(d)
            ds.add(n // d)                # парный делитель – даром
    return sorted(ds)

def prime_factors(n):
    fs = []
    d = 2
    while d * d <= n:                     # граница падает вместе с n
        while n % d == 0:
            fs.append(d)
            n //= d
        d += 1
    if n > 1:
        fs.append(n)                      # остаток – последний простой
    return fs

Почему так, а не иначе:

• isqrt(n), а не int(math.sqrt(n)). isqrt – целый корень без участия чисел с плавающей точкой: math.sqrt на очень больших числах может ошибиться на единицу из-за округления, isqrt – никогда. Заодно не нужен import math целиком.
• в is_prime чётные отсекаются одной проверкой, дальше шаг 2. После неё остаются только нечётные делители, и делений становится вдвое меньше.
• divisors идёт только до корня. Каждый найденный делитель d сразу приносит пару n // d, поэтому просматривать вторую половину диапазона незачем. Множество вместо списка – чтобы у точного квадрата (36 = 6 · 6) корень не попал в ответ дважды; sorted в конце возвращает делители по возрастанию.
• prime_factors проверяет d * d <= n для текущего, уже поделённого $n$. Вынули из числа множители – граница перебора опустилась вместе с ним, и проверять делители до старого корня больше не нужно. Когда цикл закончился, а остаток больше 1, этот остаток и есть последний простой множитель.
• общий приём. Если в задаче нужен только наименьший множитель или ответ «подходит / не подходит», выходите из цикла на первом же найденном делителе – полное разложение не нужно. Ровно это и делает решение типа 2.

1. Перебор с шагом 1 в задаче с делимостью. Программа не закончится до конца экзамена. Если в условии сказано «делящиеся на 1917», шаг перебора равен 1917.
2. fnmatch вызван как функция. import fnmatch и потом fnmatch(...) падает: модуль и функция внутри него называются одинаково. Нужно либо fnmatch.fnmatch(...), либо сразу from fnmatch import fnmatch.
3. Перепутаны ? и *. ? – ровно одна цифра, * – любое их количество, в том числе ноль. Отсюда и верхняя граница: звёздочку нельзя посчитать за одну цифру, она может дать и пустую строку, и две девятки.
4. «Ровно один раз содержит 16» проверено как '16' in str(p). Это «хотя бы один раз»: число, в записи которого «16» встретилось дважды, от числа с одним «16» такая проверка не отличает, и лишние числа молча попадают в ответ. Нужен str(p).count('16') == 1.
5. Во второй столбец напечатано q вместо p. Условие просит наименьший множитель, а n // p – это наибольший.