Даны три целых числа 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$. Также есть два случая:
- Количество членов последовательности четно (а следовательно степень $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}})$
- Количество членов последовательности нечетно (степень $m$ четная), тогда от последовательности $(1 + x + x^2 + \ldots + x^m)$ можно отделить последний член $x^m$ и тогда ситуация будет сведена к первому случаю.
Для возведения $x$ в степень будем использовать алгоритм быстрого возведения в степень, а результат брать по модулю $m$.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> using namespace std; __int128_t n; __int128_t pow(__int128_t a, __int128_t b) { __int128_t res = 1; while (b) if (b % 2) { res = (res * a) % n; b--; } else { a = (a * a) % n; b = b / 2; } return res; } __int128_t f(__int128_t x, __int128_t m) { if (m == 0) return 1; else if (m % 2) return f(x, m / 2) * (pow(x, (m + 1) / 2) + 1) % n; else return (f(x, m - 1) + pow(x, m)) % n; } int main() { int counter; cin >> counter; for (int c = 0; c < counter; ++c) { size_t x, m, nn; cin >> x >> m >> nn; n = __int128_t(nn); cout << (size_t) f(__int128_t(x), __int128_t(m)) << "\n"; } } |
Код на ideone
Задача на e-olymp