e-olymp 8655. Простая сумма

Даны три целых числа x, m и n. Вычислите $(1 + x + x^2 + \ldots + x^m) (mod\quad n)$.

Задача взята с сайта e-olymp

Входные данные

Первая строка содержит количество тестов. Каждая следующая строка содержит три целых числа $x, m$ и $n (1 \le x, m, n \le 10^{16})$.

Выходные данные

Для каждого теста выведите ответ в отдельной строке.

Тесты

Входные данные Выходные данные
1 1000 1 10000 1001
1 999999999999999 999999999999999 13 8
1 99999999999999 99999999999999 23 8
1 3 2 5 3

Алгоритм

Для решения этой задачи можно использовать следующий алгоритм. Сумму данной последовательности будем считать рекурсивно. Базой рекурсии является случай когда степень $m = 0$. Также есть два случая:

  1. Количество членов последовательности четно (а следовательно степень $m$ нечетная), тогда заметим что $(1 + x + x^2 + \ldots + x^m)$ можно представить как $(1 + x + x^2 \ldots +x^{\frac{m}{2}}) + x^{\frac{m+1}{2}} \cdot (1 + x + x^2 + \ldots + x^{\frac{m}{2}}) = $ $= (1 + x + x^2 + \ldots + x^{\frac{m}{2}}) \cdot (1 + x^{\frac{m+1}{2}})$
  2. Количество членов последовательности нечетно (степень $m$ четная), тогда от последовательности $(1 + x + x^2 + \ldots + x^m)$ можно отделить последний член $x^m$ и тогда ситуация будет сведена к первому случаю.

Для возведения $x$ в степень будем использовать алгоритм быстрого возведения в степень, а результат брать по модулю $m$.

Код на ideone
Задача на e-olymp

A119е

Задача. Вычислить бесконечную сумму с заданной точностью [latex]\varepsilon[/latex]([latex]\varepsilon[/latex]>0). Считать что требуемая точность достигнута, если несколько первых слагаемых и очередное слагаемое оказалось по модулю меньше, чем [latex]\varepsilon [/latex], это и все последующие слагаемые можно уже не учитывать.
Вычислить:
[latex]\sum _{ i=0 }^{ \infty }{ \frac { 1 }{ { 4 }^{ i }+{ 5 }^{ i+2 } } }[/latex]

[latex]\varepsilon[/latex] [latex]r[/latex]
0.09 0
0.02 0.0384615
0.000 7 0.0477735
0.000 056 0.0481501
0.000 000 4 0.0481658

Давайте сразу же упростим заданную сумму:
[latex]\sum _{ i=0 }^{ \infty }{ \frac { 1 }{ { 4 }^{ i }+{ 5 }^{ i+2 } } } = \sum _{ i=0 }^{ \infty }{ \frac { 1 }{ { 4 }^{ i }+{ 5 }^{ i }*25 } }[/latex]

Из выше описанного следует что если обозначить слагаемые в знаменателе как [latex]a[/latex] и [latex]b[/latex] соответственно, то изначально их нужно инициализировать как [latex]a=1[/latex], a [latex]b=25[/latex], то следует каждый раз умножать [latex]a[/latex] на четыре, а [latex]b[/latex] на пять, чтобы получить нужную нам последовательность. Осталось только сделать цикл который будет находить каждый элемент последовательности и прибавлять его к переменной [latex]r[/latex] в которой мы будем хранить результат, при этом цикл будет работать только пока текущий элемент последовательности больше заданного нам числа [latex]\varepsilon[/latex]. После нарушения условия цикла мы выводим полученную сумму последовательности которая хранится у нас в переменной [latex]r[/latex].

Код программы: http://ideone.com/9nYtod.