Вычисление суммы геометрических рядов (mod m)

Ответ 1

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

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

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

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

Если я ^ m конгруэнтно к 0 mod p_i, сумма тривиально равна 0.

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

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

S = sum (j = 0 to k, (i ^ m) ^ j) = ((i ^ m) ^ (k + 1) - 1)/(i ^ m - 1)

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

Если формула геометрических сумм неприменима для некоторого p_i, вы можете изменить порядок вычислений, поэтому вам нужно только перебирать от 1 до p_i вместо 1 к k, воспользовавшись тем, что термины повторяются с периодом не более p_i.

(Так как ваша серия не содержит j = 0, то значение, которое вы хотите, на самом деле является S-1.)

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

Ответ 2

Это алгоритм для аналогичной проблемы, с которой я столкнулся

Вероятно, вы знаете, что можно вычислить мощность числа в логарифмическом времени. Вы также можете сделать это для вычисления суммы геометрических рядов. Поскольку имеет место, что

1 + a + a^2 + ... + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + ... + (a^2)^n),

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

Таким образом, вам не требуется деление, поэтому вы можете взять оставшуюся часть суммы (и промежуточных результатов) по модулю любого числа, которое вы хотите.

Ответ 3

Исходя из подхода @braindoper полного алгоритма, который вычисляет

1 + a + a^2 + ... +a^n mod m

выглядит так в Mathematica:

geometricSeriesMod[a_, n_, m_] := 
   Module[ {q = a, exp = n, factor = 1, sum = 0, temp},

   While[And[exp > 0, q != 0],
     If[EvenQ[exp],
       temp = Mod[factor*PowerMod[q, exp, m], m];
       sum = Mod[sum + temp, m];
       exp--];
     factor = Mod[Mod[1 + q, m]*factor, m];
     q = Mod[q*q, m];
     exp = Floor[ exp /2];
   ];

   Return [Mod[sum + factor, m]]
]

Параметры:

• a - это "отношение" ряда. Это может быть любое целое число (включая нулевые и отрицательные значения).
• n является наивысшим показателем ряда. Допустимыми являются целые числa >= 0.
• m - это целочисленный модуль!= 0

Примечание. Алгоритм выполняет операцию Mod после каждой арифметической операции. Это важно, если вы переписываете этот алгоритм на язык с ограниченной длиной слова для целых чисел.

Ответ 4

Это можно сделать с помощью метода повторного квадратирования, который является O(log(k)) time или O(log(k)log(m)) time, если вы считаете m переменная.

В общем случае a[n]=1+b+b^2+... b^(n-1) mod m можно вычислить, отметив, что:

• a[j+k]==b^{j}a[k]+a[j]
• a[2n]==(b^n+1)a[n]

Второй, являющийся следствием первого.

В вашем случае b=i^m можно вычислить в O(log m) времени.

Следующий код Python реализует это:

def geometric(n,b,m):
    T=1
    e=b%m
    total = 0
    while n>0:
        if n&1==1:
            total = (e*total + T)%m
        T = ((e+1)*T)%m
        e = (e*e)%m
        n = n/2
        //print '{} {} {}'.format(total,T,e)
    return total

Этот бит магии имеет математическую причину - операцию над парами, определенную как

(a,r)@(b,s)=(ab,as+r)

является ассоциативным, и правило 1 в основном означает, что:

(b,1)@(b,1)@... n times ... @(b,1)=(b^n,1+b+b^2+...+b^(n-1))

Повторное возведение в квадрат всегда работает, когда операции ассоциативны. В этом случае оператор @ равен O(log(m)) времени, поэтому повторное возведение в квадрат занимает O(log(n)log(m)).

Один из способов взглянуть на это состоит в том, что экспоненциальная матрица:

[[b,1],[0,1]]^n == [[b^n,1+b+...+b^(n-1))],[0,1]]

Вы можете использовать аналогичный метод для вычисления (a^n-b^n)/(a-b) modulo m, поскольку при экспоненциальном экспонировании матрицы:

[[b,1],[0,a]]^n == [[b^n,a^(n-1)+a^(n-2)b+...+ab^(n-2)+b^(n-1)],[0,a^n]]