Сумма геометрической прогресии по модулю числа

[AlexSmith31]

Здравствуйте!
Подскажите пожалуйста, возможно ли найти сумму $S$ геометрической прогресии $1+a^1+a^2+...+a^n по модую числа $m$, т. е. $1+a^1+a^2+...+a^n =_{\mod m} S$
без явного вычисления суммы $S=(\sum_{i=0}^n {(a^i \mod m)}) \mod m$?

У меня стоит задача вычисления этой суммы по модулю за разумное время (желательно лучше $O(n)$), при чем число $n$ может быть очень большим.

Может быть как-нибудь воспользоваться $1+a^1+a^2+...+a^n=\frac {1-a^n}{ 1-a}$?
Кто что может посоветовать, в какую сторону копать?
Заранее спасибо.

[Sonic86]

AlexSmith31 в сообщении #495138 писал(а):

Может быть как-нибудь воспользоваться $1+a^1+a^2+...+a^n=\frac {1-a^n}{ 1-a}$?

Ну вот, Вы сами все и написали, нужно было лишь побольше решимости.
Случай $a=1$ обрабатываем отдельно (понятно как).
Далее, зависит от взаимной простоты $a-1$ и $m$. В случае простого $m$ при $a \neq 1, a<m$ сразу получаем, что $a-1$ и $m$ взаимно просты, и тогда нужно лишь вычислить $(1-a)^{-1} \mod m$, что делается за $O(\ln n)$ алгоритмом Евклида. Ну и так же при простом $m$ функция Эйлера $\varphi (m)=m-1$, а значит степень $a^n$ можно заменить на $a^{n \mod (m-1)}$. Ну и остается вспомнить как быстро возводить в степень по модулю (там $O(\ln ^k n)$, $k$ не помню).

При не простом $m$ ситуация посложнее. Можно раскладывать $m$ на простые множители (если $m$ велико - это уже отдельная проблема), задача сведется к вычислению функции по модулю степени простого числа $p^a$. Остаток по модулю $m$ будет собираться из остатков по модулю $p^a$ с помощью китайской теоремы об остатках. Тут почти так же, за исключением того, что при $a:a \equiv 1 \pmod p$ нет обратного элемента у $1-a$. Об это надо отдельно подумать. Если пока все устраивает - могу подумать

-- Сб окт 22, 2011 17:23:39 --

Sonic86 в сообщении #495159 писал(а):

Тут почти так же, за исключением того, что при $a:a \equiv 1 \pmod p$ нет обратного элемента у $1-a$.

Тут, наверное, надо так: если $a=1+bp^r$, $p \not | b$, то по биному Ньютона $\frac{a^n-1}{a-1}=\frac{(bp^r+1)^n-1}{p^r}=\frac{...+C_n^2(bp^r)^2+C_n^1(bp^r)}{bp^r}=...+C_n^2(bp^r)+C_n^1$ - получаем сумму по степеням $(p^r)^j$. При $j>j_0$ при $rj_0>a$ имеем $(bp^r)^j \equiv 0 \pmod p^a$ - полученную сумму (не путать с исходной!) можно обрубить на члене $j=j_0$ и подсчитать. При малых $b,r$ можно вычислить и в лоб.

Что-то как-то сложно вышло Может товарищи суровые прогеры знают более легкий метод?

Это все конечно для целых $a$.

[AlexSmith31]

Спасибо за ответ!

Да, кстати в первом посте я забыл упомянуть что $a, m \in N, \\ 1 \leqslant a, m \leqslant 2 \cdot 10^4$

Правильно ли я понимаю что в случае $gcd(a-1, m)=1$ чтобы найти $\frac{1}{1-a}$ надо решить диофантово уравнение?
$\frac{1}{1-a} =_{\mod m} x \\ 1 =_{\mod m} (1-a)x \\ 1 = (1-a)x + my $

Цитата:

Ну и остается вспомнить как быстро возводить в степень по модулю (там $O(\ln ^k n)$, $k$ не помню).

Насколько я помню это называется бинарное возведение в степень,
$a^n= \left\{ \begin{array}{l l} (a^{n/2})^2 & \quad \text{if $n$ is even}\\ a^{n-1}\cdot a & \quad \text{if $n$ is odd}\\ \end{array} \right.$
Вычислительная сложность которого $O(\log_2 n)$

[Sonic86]

AlexSmith31 в сообщении #495249 писал(а):

$\frac{1}{1-a} =_{\mod m} x $

AlexSmith31 в сообщении #495138 писал(а):

$1+a^1+a^2+...+a^n =_{\mod m} S$

Что это за странное обозначение?

AlexSmith31 в сообщении #495249 писал(а):

$\frac{1}{1-a} =_{\mod m} x \\ 1 =_{\mod m} (1-a)x \\ 1 = (1-a)x + my $

Да. Только $1-a$ тут проще как-то переобозначить, чтоб не так громоздко выглядело.

AlexSmith31 в сообщении #495249 писал(а):

Вычислительная сложность которого $O(\log_2 n)$

Вообще-то после возведения в степень полученные результаты нужно еще перемножить, что дает еще как минимум $O (\ln n)$ - уже как минимум $O(\ln ^2 n)$. В любом случае быстрее алгоритма нету.

[maxal]

Вычислить $\frac{1-a^n}{1-a}$ по модулю $m$ в общем случае проще так:

$$\frac{(1-a^n) \bmod ((1-a)\cdot m)}{1-a}.$$

А обратный по модулю находится с помощью расширенного алгоритма Евклида.

[venco]

AlexSmith31, вы, похоже, вот это решаете: http://dxdy.ru/topic50168.html

[Sefko]

Что-то как-то тут очень все сложное предлагают. Так мне кажется. Хотя, может быть и так, что я чего-то не понял.
1. $(ab)\mod m = ((a\mod m)(b\mod m))\mod m.$
2. $a^n+a^{n-1}+…+a+1=(...(a+1)a+1)…$ (детская схема Горнера вычисления полинома).

Объединяя 1 и 2 получаем относительно тупой алгоритм типа

int xaxa(int a, int n, int m)
  { int retc;
     a%=m;
     retc=(a+1)%m;
     for(int i=1; i<n; i++) retc=(retc*a+1)%m;
    return retc;
  }

Это не самый шустрый алгоритм, но и не такой уж медленный. Excel у меня выдал ~760 вычислений функции в секунду (аргументы взяты с потолка $a=11113$, $n=12017$, $m=13503$). Вроде как его сложность – $O(n)$.
Главное достоинство алгоритма, на мой взгляд, – простота.

[maxal]

Sefko в сообщении #495775 писал(а):

Вроде как его сложность – $O(n)$.

А у нас сложность $O(\log n)$ -- почуствуйте разницу.

[Sefko]

maxal в сообщении #495778 писал(а):

Sefko в сообщении #495775 писал(а):

Вроде как его сложность – $O(n)$.

А у нас сложность $O(\log n)$ -- почуствуйте разницу.

Пока чувствую разницу в том, что алгоритм сложности $O(n)$ конкретно нарисован и даже испытан, а об алгоритме сложности $O(log(n))$ имеются только приблизительные разговоры, что может быть, стоит попробовать так...

Это во-первых. Во-вторых, алгоритм сложности $O(n)$ - это несколько строк текста. Если отбросить обрамление, то это всего один простейший цикл с одним оператором. А гипотетический алгоритм сложности $O(log(n))$ проглядывается из неотчетливого разговора в виде небольшого чемодана. До каких размеров вырастет этот чемодан при ласковых поглаживаниях в процессе реализации - непонятно.
Это имеет прямое отношение к оценке сложности алгоритма: размер текста - не только влияет на вероятность ошибки, но и связан с величиной коэффициента, который скрывается за буковкой $O$.

В-третьих, в этих же разговорах имеются утверждения о том, что сложность гипотетического алгоритма вовсе не $O(log(n))$, а $O(log^2(n))$, которые вроде как никто не опроверг.

Кстати, о птичках. Оптимальный алгоритм имеет таки сложность порядка $O(ln(n))$, а не $O(ln^2(n))$ - так мне кажется. И размер его - не чемодан, а небольшой бумажник (полное оформление уложится в пару десятков строк, я думаю). Но в обсуждении на ветке нет даже намека на путь к этому алгоритму.

Все написанное в этом сообщении, если я не прав, очень легко опровергается приведением текста реального алгоритма, реализующего тот алгоритм, который "А у нас".

[maxal]

Sefko в сообщении #495867 писал(а):

В-третьих, в этих же разговорах имеются утверждения о том, что сложность гипотетического алгоритма вовсе не $O(log(n))$, а $O(log^2(n))$, которые вроде как никто не опроверг.

Вы путаете $O(\log^2(n))$ с $O(\log_2(n))$ - разговор шел про второе.

А реализация - в данном случае типовая, никаких тонкостей. Всего здесь требуется одно возведение в степень $n$ по модулю числа $(a-1)m$ (c помощью бинарного алгоритма), одно вычитание и одно деление.

[Sefko]

maxal в сообщении #495869 писал(а):

Вы путаете $O(\log^2(n))$ с $O(\log_2(n))$ - разговор шел про второе.

Если я что-то путаю, то, значит, путаю - то есть не вижу своей ошибки. Проверил еще раз - все равно не вижу. То есть не нашел опровержения вот этого утверждения.

Sonic86 в сообщении #495272 писал(а):

Вообще-то после возведения в степень полученные результаты нужно еще перемножить, что дает еще как минимум $O (\ln n)$ - уже как минимум $O(\ln ^2 n)$. В любом случае быстрее алгоритма нету.

maxal в сообщении #495869 писал(а):

А реализация - в данном случае типовая, никаких тонкостей. Всего здесь требуется одно возведение в степень $n$ по модулю числа $(a-1)m$ (c помощью бинарного алгоритма), одно вычитание и одно деление.

И опять двадцать пять. Это я все о своей путанице.

Уважаемый maxal!
Не могли бы Вы, раз уж начали пытаться меня распутать, указать ссылку на конкретное сообщение на ветке, где приводится схема того самого типового алгоритма, который «А у нас…». Ну не вижу я сообщения, к которому можно было бы без сомнений отнести процитированное мною Ваше утверждение.

Прошу прощения. Просмотрел еще раз и нашел. Видимо, Вы имеете в ввиду вот это сообщение. Там, правда, мне непонятно последнее утверждение, ну, да ладно. Если бы заметил сразу, то вооюще не стал бы выступать на этой ветке.

Но этого, к сожалению, недостаточно для моего распутывания. Дело в том, что не Вы первый приводите здесь ссылку на бинарный алгоритм возведения в степень. Но я не заметил здесь никаких намеков на бинарный алгоритм возведения в степень по модулю. А именно в этом мне мерещится некая тонкость, без учета которой внутрь главного цикла придется вводить операцию деления. А обсуждения этой тонкости я на ветке опять же не заметил.

[nnosipov]

Sefko в сообщении #495880 писал(а):

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

А нет здесь никакой тонкости. Есть одна простая формула.

[maxal]

Sefko в сообщении #495880 писал(а):

Прошу прощения. Просмотрел еще раз и нашел. Видимо, Вы имеете в ввиду вот это сообщение. Там, правда, мне непонятно последнее утверждение, ну, да ладно.

Да, оно. Последнее утверждение там отвечает на другой вопрос, ранее заданный AlexSmith31, и к указанной мной формуле прямого отношения не имеет.

Sefko в сообщении #495880 писал(а):

Но этого, к сожалению, недостаточно для моего распутывания. Дело в том, что не Вы первый приводите здесь ссылку на бинарный алгоритм возведения в степень. Но я не заметил здесь никаких намеков на бинарный алгоритм возведения в степень по модулю. А именно в этом мне мерещится некая тонкость, без учета которой внутрь главного цикла придется вводить операцию деления. А обсуждения этой тонкости я на ветке опять же не заметил.

Ну это довольно стандартная вещь - при возведении в степень по некоторому модулю делается всё то же самое, что и при обычном возведении с той лишь разницей, что каждое умножение производится по нашему модулю. Даже если считать, что умножение по модулю делается в лоб обычным умножением с последующим делением произведения на модуль (с целью получения остатка от деления), общее количество обычных арифметических операций возрастает лишь в два раза.

[AlexSmith31]

maxal в сообщении #495320 писал(а):

Вычислить $\frac{1-a^n}{1-a}$ по модулю $m$ в общем случае проще так:

$$\frac{(1-a^n) \bmod ((1-a)\cdot m)}{1-a}.$$

А обратный по модулю находится с помощью расширенного алгоритма Евклида.

maxal, а почему $(1-a^n)$ вычисляется именно по такому модулю $((1-a)\cdot m)$?

[maxal]

AlexSmith31 в сообщении #495905 писал(а):

maxal, а почему $(1-a^n)$ вычисляется именно по такому модулю $((1-a)\cdot m)$?

Чтобы $1-a$ можно было сократить. Дело в том, что сравнение $a\cdot c \equiv b\cdot c\pmod{m\cdot c}$ для $c\ne 0$ эквивалентно $a \equiv b\pmod{m}$ (заметьте, что на $c$ здесь не накладывается никаких условий, кроме неравенства нулю; в частности, оно вполне может быть не взаимно-просто с $m$).
Нам вот надо поделить на $1-a$ (причем известно, что делимое $1-a^n$ на него делится нацело - это важно), поэтому мы и вносим сначала его в качестве множителя в модуль, а потом легким движением руки сокращаем.