Делители и маски чисел

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

Делимость, остаток и кратность

Натуральными здесь называются целые положительные числа, начиная с единицы. Натуральное число d является делителем натурального числа n, если существует натуральное q, для которого n=dq. В таком случае n называется кратным d. Это одно отношение с двух сторон: 4 делитель 20, а 20 кратно 4.

Для любых натуральных n,d деление с остатком имеет вид n=dq+r, где 0\le r<d. Здесь q целая часть частного, r остаток. Делимость означает r=0. Поэтому n % d == 0 проверяет делимость, а n // d после успешной проверки даёт точное частное.

Остаток также связывает значение с десятичной записью. Любое неотрицательное целое число можно записать как n=10q+r, где r последняя цифра. Следовательно, n % 10 выделяет одну последнюю цифру, n % 100 последние две. Условие окончания на 63 выражается как n % 100 == 63. Остаток при делении на другое основание, например на семь, сам по себе десятичного окончания не задаёт.

Почему делители находятся парами

Из равенства n=dq следует, что делителями являются оба множителя. Переход d\mapsto n/d связывает их в пару. Если меньший элемент пары больше \sqrt n, то больший тоже больше корня и произведение превышает n. Это противоречие показывает: в каждой паре хотя бы один делитель не превосходит корня.

Поэтому поиск до корня включительно находит все пары. У 20 получаются (1,20), (2,10), (4,5). У 49 есть пара (7,7). Равенство элементов возможно только у полного квадрата; при подсчёте различных делителей совпавшее значение учитывается один раз.

Внутри пары рост одного делителя уменьшает другой. Если у числа есть делители кроме единицы и самого числа, минимальному из них соответствует максимальный. Для суммы этих двух крайних значений достаточно найти первый делитель от двух до корня. Но это сокращение опирается на конкретную задачу: если требуется сумма всех делителей или делитель с определённым окончанием, остальные пары остаются значимыми.

Множество разрешённых делителей задаётся условием. Единица и само число всегда делят натуральное число, но могут исключаться из вычисления. В примере суммы всех различных делителей ↗ для 20 получается 42. После удаления единицы и самого числа сумма равна 42-1-20=21. Сумма крайних оставшихся значений равна уже 2+10=12: это третья, самостоятельная величина.

Простое число и разложение

Простое число имеет ровно два натуральных делителя: единицу и само себя. Число 1 не простое, потому что делитель у него только один. Число больше единицы, у которого есть другие делители, называется составным. По свойству пар составность обнаруживается хотя бы одним делителем от двух до корня включительно.

Каждое натуральное число больше единицы представляется произведением простых множителей; с точностью до их порядка разложение единственно. Например, 12=2\cdot2\cdot3. Если деление на найденный простой множитель выполняется несколько раз, все повторения входят в разложение. Количество повторений называется кратностью простого множителя.

Различные простые делители образуют множество без повторений. У 12 оно равно \{2,3\}: различных простых делителей два, а множителей в разложении три. Это различие определяет смысл ограничений "ровно два простых множителя" и "число различных простых делителей". Число 49=7\cdot7 имеет два множителя с учётом повторения и только один различный простой делитель.

Максимальный простой делитель не обязательно равен максимальному натуральному делителю меньше самого числа. У 12 это соответственно 3 и 6. Поэтому простота делителя должна быть установлена отдельно, например разложением числа. Если разрешён только один простой делитель, минимум и максимум совпадают. В сумме двух крайних значений он участвует дважды: для 49 получается 7+7=14.

Отсутствие разрешённых делителей тоже требует определения результата. Если само число исключено, простое число не оставляет ни одного простого делителя. Значение ноль в таких задачах является соглашением условия, а не результатом вычисления минимума пустого множества. Проверка наличия элементов должна предшествовать вычислению минимума и максимума.

Числовое свойство и свойство записи

Для проверки простоты нужны делители, для полного квадрата целый квадратный корень. Число M\ge0 является полным квадратом, если для k=\lfloor\sqrt M\rfloor выполняется k^2=M. Например, 518400=720^2. В Python isqrt вычисляет именно целую часть корня, поэтому обратное возведение в квадрат даёт точную проверку.

Палиндром определяется порядком цифр: запись совпадает с перевёрнутой. Например, 94449 читается одинаково с обоих концов. Требование "содержит подстроку 43 ровно один раз" относится к соседним символам, а не к отдельному наличию цифр. В 4343 такая подстрока встречается дважды. Если требование задано для каждого множителя, оно проверяется у каждого отдельно, а не у записи их произведения.

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

Маска как множество допустимых записей

Маска числа состоит из заданных цифр и знаков подстановки. Цифра требует точного совпадения; ? обозначает ровно одну цифру, * любую последовательность цифр, включая пустую. Маска сопоставляется со всей обычной десятичной записью натурального числа, без ведущих нулей.

В маске с переменной серединой 1234*54 ↗ пустая середина даёт 123454, а подстановка 00 даёт 12340054. Нули во втором примере внутренние: они не удаляются. Соответствие маске ещё не означает выполнения остальных требований задачи, например делимости.

Когда первый разряд уже задан ненулевой цифрой, каждый вопросительный знак добавляет один разряд и десять возможных цифр. Поэтому две независимые позиции дают 10^2=100 вариантов. Звёздочка фиксированной длины k внутри записи даёт 10^k строк, но сначала должны быть определены все допустимые длины. Если подстановка затрагивает первый разряд, ведущий ноль исключается. Верхняя числовая граница делает такой перебор конечным; граничное число проверяется отдельно, если имеет на один разряд больше остальных.

Полнота перебора и порядок ответа

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

Формулировка "первые пять" требует возрастания кандидатов и остановки после пяти успехов. Формулировка "все числа не больше границы" требует пройти допустимый диапазон до конца. При генерации подстановок порядок получения строк может не совпадать с порядком чисел, поэтому нужна числовая сортировка. Повторное получение одного числа не создаёт новую строку ответа.

От свойств к решению

Почему сумму крайних натуральных делителей можно найти по первому делителю, а сумму крайних простых так находить нельзя? Как перебрать маску с пустой или непустой звёздочкой, сохранив полный и упорядоченный ответ? Ответы показаны в статье "Задание №25. Делители и маски чисел": от первых проверок кандидатов до программ и итоговых таблиц.