Делимость и делители

Школьные признаки делимости — «на 3, если сумма цифр делится на 3» — в программировании почти не нужны. У нас есть операция остатка, и любой вопрос о делимости сводится к ней:

if n % 3 == 0:
    print("делится на 3")

Никакой суммы цифр, никаких особых случаев для 7 и 11. Одна операция для любого делителя.

Две операции, связанные одним равенством

Целочисленное деление // и остаток % всегда согласованы:

Это равенство держится всегда, и из него следует всё остальное.

Отрицательные числа: осторожно

Здесь Python ведёт себя не так, как C++ или Java, и на этом регулярно попадаются.

-7 // 3     # -3, а не -2 — деление округляется вниз, а не к нулю
-7 % 3      #  2, а не -1 — остаток всегда неотрицательный

Проверим равенство: $(-3) \cdot 3 + 2 = -7$. Сходится.

Практический вывод: в Python остаток от деления на положительное число никогда не бывает отрицательным. Это удобно — можно смело использовать a % k как номер ячейки в списке, не боясь получить минус. В C++ такой код упал бы.

Найти все делители числа $10^{12}$ перебором до самого числа — триллион действий, то есть часы. К счастью, перебирать столько не нужно.

Ключевое наблюдение. Если $i$ делит $n$, то и $n / i$ делит $n$. Делители разбиваются на пары, и в каждой паре один множитель не больше $\sqrt{n}$, а другой не меньше.

Значит достаточно перебрать $i$ до корня — второй делитель каждой пары получится бесплатно:

i = 1
while i * i <= n:
    if n % i == 0:
        # нашли пару: i и n // i
        ...
    i += 1

Было $10^{12}$ шагов, стало $10^6$. Это доли секунды.

Пара, которая совпадает сама с собой

Единственная тонкость — полные квадраты. У числа 36 пара $(6, 6)$ состоит из одного и того же делителя, и учитывать его надо один раз, а не два:

if n % i == 0:
    count += 1 if i * i == n else 2

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

Сравнивайте i * i <= n, а не i <= n ** 0.5

Второй вариант считает вещественный корень, и вопрос «а точно ли он вычислен верно на восемнадцатизначном числе» приходится обдумывать отдельно. С i * i <= n вопрос не возникает вовсе: там только целые числа. Если корень всё же нужен явно, берите math.isqrt(n) — она целочисленная и точная.

Сколько примерно шагов нужно, чтобы найти все делители числа $10^{12}$?

Наибольший общий делитель двух чисел ищется способом, которому больше двух тысяч лет. В основе — одно равенство:

Почему оно верно? Любой общий делитель $a$ и $b$ делит и их разность, а значит делит остаток $a \bmod b$. И наоборот. Значит у пар $(a, b)$ и $(b, a \bmod b)$ множества общих делителей совпадают целиком — а раз так, совпадают и наибольшие.

while b != 0:
    a, b = b, a % b
print(a)          # когда второе стало нулём, ответ в первом

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

В Python писать это руками не нужно: math.gcd(a, b) уже есть. Но знать, почему оно работает, — нужно.

НОК через НОД

Записывать это стоит так:

lcm = a // gcd(a, b) * b        # сначала делим, потом умножаем

В Python целые числа неограниченные, поэтому a * b // gcd(a, b) тоже сработает. Но привычку делить первым лучше завести сейчас: в C++ произведение двух миллиардов уже не помещается в 64 бита, а после деления — помещается.

Для нескольких чисел

И НОД, и НОК собираются по одному числу за раз: НОД(a, b, c) = НОД(НОД(a, b), c). То же и для НОК.

Сколько натуральных делителей у числа 36? Введите целое число.

Есть приём, который выглядит несерьёзно, а решает целый класс задач: группировка по остатку.

Задача: сколько в списке пар чисел, сумма которых делится на $k$?

Перебор пар — до двадцати миллиардов проверок. Но сумма делится на $k$ тогда и только тогда, когда остатки слагаемых дают в сумме $k$ или ноль. А остатков всего $k$ штук.

counts = [0] * k
for value in a:
    counts[value % k] += 1

Теперь ответ собирается из количеств: числа с остатком $r$ образуют пары с числами с остатком $k - r$. Отдельно считаются два случая — остаток 0 и, если $k$ чётное, остаток $k/2$: там пары составляются внутри одной группы, и их количество равно $\frac{c(c-1)}{2}$.

Тот же приём работает для разностей: разность делится на $k$ ровно тогда, когда у чисел одинаковый остаток.

Обратите внимание, чем мы заплатили: временем $O(n + k)$ вместо $O(n^2)$ и списком на $k$ ячеек. Это типичный обмен для задач на делимость — перебор заменяется подсчётом по группам.

Квадрат посчитан дважды. Разобран выше. Проверяйте решение на 36, 49, 100.

Перебор до $n$ вместо корня. Проходит на маленьких тестах и получает превышение времени на больших. Признак: решение верное, а вердикт по времени.

Забыт случай $n = 1$. У единицы ровно один делитель, наименьшего делителя больше единицы у неё нет, а наибольшего собственного — тоже. Такие задачи почти всегда содержат $n = 1$ в тестах.

НОД нуля. gcd(0, x) = x, и это не ошибка, а определение: на ноль делится всё. А gcd(0, 0) = 0. Если в задаче встречаются нули, проверьте, что ваш цикл их переживает.

НОК без деления первым. В Python не страшно, в других языках — переполнение. Заводите привычку сразу.

Пустой список для остатков. counts = [0] * k при $k = 1$ даёт список из одной ячейки, и все числа попадают в неё. Это верно, но проверьте, что формулы с $k - r$ и $k/2$ на таком $k$ не выходят за границы.

Как проверять себя

• $n = 1$ и $n$ простое;
• полный квадрат: 36, 49, 100;
• число с очень многими делителями: у 963 761 198 400 их 6720;
• $k = 1$ в задачах на остатки — тогда подходит вообще всё.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Почти везде работают три инструмента: остаток, перебор до корня и НОД. Если задача выглядит так, будто нужен перебор до $n$, — почти наверняка нужен перебор до корня.

И следите за границами: числа в этом занятии доходят до $10^{18}$. В Python это не проблема, но проверьте, что вы не считаете лишнего.

Задача: «дано $n$ от 1 до $10^{12}$; выведите количество его натуральных делителей».

Ученик написал:

n = int(input())

count = 0
i = 1
while i * i <= n:
    if n % i == 0:
        count += 2
    i += 1

print(count)

Перебор до корня сделан правильно, по времени решение проходит. На числах 12, 30 и 1000 ответ верный.

Найдите вход, на котором решение ошибается, объясните причину и предложите исправление.