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

MLoops12

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел n > 0 (количество столбцов) и m > 0 (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.
Замечание 2. Многоточие означает продолжение последовательности
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться  Онлайн-энциклопедией целочисленных последовательностей.

 

Тесты

n m k Результат
15 9 4
 10  7  3
 12  5  2
 25  15  7

 

Код программы

Решение

Закономерности в таблице

  1. Через каждые [latex]k[/latex] строк, начиная с нулевой, встречается строка, в которой нулевой и каждый [latex]k[/latex]-й символы — «+», а остальные — «-«. Такие строки разделяют одинаковые [latex]k[/latex]-местные блоки строк.
  2. Каждая строка блока строк содержит, в свою очередь, [latex]k[/latex]-местные блоки символов (эти блоки уже разные), разделенные символами «|». В каждой строке из блока два вида блоков символов (далее блок 1 и блок 2). Все нечетные блоки имеют вид блока 1, четные — блока 2.
  3. Блок 1 содержит числа по возрастанию, начиная с номера строки в блоке строк, до [latex]k[/latex] включительно, т.е. числа из сегмента [latex][i ; k][/latex], где [latex]i[/latex] — номер строки в блоке строк. После них в блоке записаны числа от [latex]1[/latex]  до номера строки в блоке, не включая сам этот номер, т.е. числа из полусегмента [latex][1 ; i)[/latex].
  4. Блок 2 каждой строки содержит те же числа, что и блок 1, но записанные в противоположном порядке.

Реализация

Программа содержит один большой цикл, перебирающий строки. Причем, этот цикл содержит 2 счетчика строк — один считает номер текущей строки в таблице, а второй — в блоке строк. В этот цикл вложен цикл, перебирающий блоки, а в нем, в свою очередь, цикл, записывающий блок. Чтобы цикл вывода блоков символов (строк) не выводил лишние символы (строки), выводящие символы (строки) циклы, которые находятся внутри них, должны содержать проверку не только на окончание блока, но и на окончание таблицы (само собой, циклы, выводящие блоки тоже имеют проверку на конец таблицы).

ссылка на код на ideone

Mloops 5

Условие задачи

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0 [/latex] (количество столбцов) и [latex] m>0 [/latex] (количество строк): +++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*++ .

Задача находится здесь.

Тесты

n m Таблица
1 25 8 +++++*+++++*+++++*+++++*+
++++*+++++*+++++*+++++*++
+++*+++++*+++++*+++++*+++
++*+++++*+++++*+++++*++++
+*+++++*+++++*+++++*+++++
*+++++*+++++*+++++*+++++*
+++++*+++++*+++++*+++++*+
++++*+++++*+++++*+++++*++
2 6 6 +++++*
++++*+
+++*++
++*+++
+*++++
*+++++
3 2 5 ++
++
++
++
+*

Алгоритм решения

Таблица, которую необходимо вывести на экран представляет собой определённую последовательность. Каждый символ таблицы имеет номера столбца и строки (нумерация от 0 до n или m не включительно). Для этого задаём счётчики [latex] i [/latex] и [latex] j [/latex] .  Наша задача — определить закономерность появления символа [latex] \ast [/latex] в данной таблице, поскольку в иных случаях необходимо вывести символ [latex] + [/latex]. В первой строке «звёздочка» встречается в данной таблице в [latex] 6,12,18,24[/latex] столбцах. Во второй строке «звёздочка» находится в [latex] 5,11,17,23[/latex] столбцах. В последующих строках ситуация аналогичная. Можно заметить, что символ [latex] \ast [/latex] стоит на позициях, при которых сумма номера строки и номера столбца делится нацело на 6. Проверяем это условие с помощью тернарной операции:

от суммы номеров столбца и строки отнимаем число [latex] 5 [/latex], поскольку нам необходимо, чтобы первыми пятью символами последовательности были плюсы.

Код программы

Ссылка на рабочий код программы находится здесь.