Расчет суммы геометрических рядов (мод м)

Question

У меня есть серия

S = i^(m) + i^(2m) + ...............  + i^(km)  (mod m)   

0 <= i < m, k may be very large (up to 100,000,000),  m <= 300000

Я хочу найти сумму. Я не могу применить формулу геометрической прогрессии (GP), потому что тогда результат будет иметь знаменатель, и тогда мне нужно будет найти модульное обратное, которое может не существовать (если знаменатель и m не взаимно просты).

Итак, я сделал альтернативный алгоритм, предполагая, что эти степени сделают цикл длины намного меньшим, чем k (потому что это модульное уравнение, и поэтому я получил бы что-то вроде 2,7,9,1,2,7 , 9,1 ....) и этот цикл повторится в вышеуказанных сериях. Таким образом, вместо итерации от 0 до k, я бы просто нашел сумму чисел в цикле, а затем вычислил количество циклов в вышеуказанном ряду и умножил их. Итак, я сначала нашел i^m (mod m), а затем умножил это число снова и снова, взяв по модулю на каждом шаге, пока я снова не достиг первого элемента.

Но когда я фактически закодировал алгоритм, для некоторых значений i я получил циклы очень большого размера. И, следовательно, потребовалось много времени для завершения, и, следовательно, мое предположение неверно.

Так есть ли какой-то другой паттерн, который мы можем выяснить? (В основном я не хочу перебирать k.) Поэтому, пожалуйста, дайте мне представление об эффективном алгоритме для нахождения суммы.

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Если i ^ m совпадает с 0 mod 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 или найдите альтернативное решение для случаев, когда у них нетривиальный GCD. Надеемся, что тот факт, что p_i является главной степенью, а также делителем m, будет полезным ... Если p_i является делителем i. условие выполняется. Если p_i является простым (в отличие от простой степени), то либо применяется особый случай i ^ m = 1, либо (i ^ m - 1) имеет мультипликативный обратный.

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

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

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

Answer 3

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

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

1. a[j+k]==b^{j}a[k]+a[j]
2. 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) по модулю m, поскольку матричное возведение в степень дает:

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

Answer 4

На основе подхода @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 является наивысшим показателем ряда. Допускаются целые числа> = 0.
• m - это целочисленный модуль! = 0

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