Вычисление суммы геометрического ряда (модификация m)

Как вы отметили, выполнение вычислений для произвольного модуля m затруднено, поскольку многие значения могут не иметь обратного мультипликативного модуля m. Однако, если вы можете решить ее для тщательно подобранного набора альтернативных модулей, вы можете объединить их, чтобы получить решение mod m.

Разложите m на p_1, p_2, p_3 ... p_n так, чтобы каждый p_i был степенью отдельного простого числа

Поскольку каждый p является отдельной степенью простого числа, они попарно взаимно просты. Если мы можем вычислить сумму ряда по каждому модулю p_i, мы можем использовать Китайскую теорему об остатках , чтобы собрать их в решение по модулю m.

Для каждого простого степенного модуля существует два тривиальных частных случая:

Если i ^ m конгруэнтно 0 по модулю p_i , сумма тривиально равна 0.

Если i ^ m конгруэнтно 1 mod p_i , то сумма конгруэнтна k mod p_i .

Для других значений можно применить обычную формулу для суммы геометрической последовательности:

S = сумма (от j = 0 до k, (i ^ m) ^ j) = ((i ^ m) ^ (k + 1) - 1) / (i ^ m - 1)

TODO: Докажите, что (i ^ m - 1) взаимно просто с p_i , или найдите альтернативное решение, когда у них есть нетривиальный НОД. Надеюсь, тот факт, что p_i является степенью простого числа, а также делителем m, будет полезен ... Если p_i является делителем i. условие выполнено. Если p_i является простым числом (в отличие от степени простого числа), то применяется либо частный случай i ^ m = 1, либо (i ^ m - 1) имеет мультипликативную инверсию.

Если формула геометрической суммы неприменима для некоторого p_i , Процедура объединения их в решение mod m описана в приведенной выше ссылке, поэтому я не буду повторять ее здесь.