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

2 thoughts on “e-olymp 8655. Простая сумма

  1. Это вроде не сильно ускорит работу но как по мне лаконичнее вместо этого b%2 писать вот так b & 1 мы же просто проверяем последний бит

Добавить комментарий