3. Пересчитать только суммы которые имеют общий делитель с i или k. Таких будет

, где

. В худшем случае i и k делятся на 2 и

. Это примерно в

быстрее первого метода и в 2 раза быстрее второго метода.
Если поменять местами числа

и

, то изменение числа Делакорта вычисляется по формуле:

Все числа

являются константами и вычислены заранее.
При вычислении

используются текущие значения

После фактического выполнения обмена

новые значения

для всех

таких, что

вычисляются по следующим формулам:

Сложность расчета

есть

, а сложность обновления всех

есть

Ускорение получается за счёт того, что

вычисляется значительно чаще чем выполняется обмен

Но можно

не хранить, а вычислять в процессе вычисления

При этом хранить

и обновлять их при фактическом выполнении обмена

В этом случае сложность вычисления

и сложность пересчёта

будет пропорциональна числу делителей

и

то есть в среднем

UPD: Исправлены формулы.