Начало
Соревнования
Разбор задачи B. Вундеркинд
Тема: модулярная арифметика, быстрое возведение в степень, периодические последовательностиСложность: выше среднего
Правила модулярной арифметики:
`(X+Y)\ mod\ M\ =\ ((X\ mod\ M)\ +\ (Y\ mod\ M))\ mod\ M`
`(X-Y)\ mod\ M\ =\ ((X\ mod\ M)\ -\ (Y\ mod\ M)\ +\ M)\ mod\ M` (в случае отрицательного результата нужно добавить к нему M)
`(X*Y)\ mod\ M\ =\ ((X\ mod\ M)\ *\ (Y\ mod\ M))\ mod\ M`
`X^P\ mod\ M\ =\ (X\ mod\ M)^P\ mod\ M`
Т.е. если к аргументам операций сложения, вычитания, умножения и возведения в степень применить остаток от деления, то результат не изменится. Это позволяет выполнять вычисления, не прибегая к длинной арифметике, в задачах, где требуется найти остаток от деления результата на `M`.
Для быстрого возведения в степень нужно воспользоваться способом, основанном на двоичном представлении показателя степени. Подобный способ, но для умножения чисел, был придуман еще 4 тысячи лет назад в Древнем Египте.
Известный российский математик Я.И.Перельман в своей книге «Занимательная арифметика» описал русский народный способ умножения. Сущность его в том, что умножение двух чисел сводится к ряду последовательных делений одного числа пополам при одновременном удвоении другого числа. Например: нужно умножить 32 на 13. Это записывается таким образом:
`32*13`
`16*26`
`8*52`
`4*104`
`2*208`
`1*416`
Деление пополам продолжают до тех пор, пока в частном не получится 1, параллельно удваивая другое число. Последнее удвоенное число и дает искомый результат. Способ основан на том, что произведение не изменяется, если один множитель уменьшить вдвое, а другой вдвое же увеличить. А в результате многократного повторения этой операции получается искомое произведение: `32*13\ =\ 1*416`.
Если приходится делить нечетное число пополам, то в этом случае от нечетного числа откидывается единица и остаток уже делится пополам; но зато к последнему числу правого столбца нужно будет прибавить все те числа этого столбца, которые стоят против нечетных чисел левого столбца: сумма и будет искомым произведением. Практически это делают так, что все строки с четными левыми числами зачеркивают; остаются только те, которые содержат налево нечетное число. Пример:
`19*17`
`9*34`
`1*272`
Сложив незачеркнутые числа, получаем правильный результат:
`17\ +\ 34\ +\ 272\ =\ 323`.
Обоснованность приема станет ясна, если принять во внимание, что
`19*17\ =\ (18\ +\ 1)*17\ =\ 18*17\ +\ 17`
`9*34\ =\ (8\ +\ 1)*34\ =\ 8*34\ +\ 34`, и так далее.
Ясно, что числа 17, 34 и т.п., утрачиваемые при делении нечетного числа пополам, необходимо прибавить к результату последнего умножения, чтобы получить произведение.
У некоторых английских авторов этот способ умножения описывается под названием «русский крестьянский способ». В Германии крестьяне также пользуются им и называют его «русским».
Не исключено, что этот способ дошел до нас из Египта. Одним из основных источников сведений о древнеегипетской математике является папирус, купленный в Луксоре шотландским антикваром Александром Генри Риндом, который сейчас хранится в Британском музее. Папирус был найден в металлическом футляре. В развернутом виде имеет 5.5 м длины при 32 см ширины. Он представляет собой собрание решений 84 задач, имеющих прикладной характер. Папирус относится примерно к 2000-1700 г. до н.э. и представляет собой копию еще более древней рукописи, переписанную писцом Ахмесом. В папирусе используется иератическая система обозначений чисел – условные знаки, которые произошли из иероглифов в результате упрощений и стилизации. В нем есть четыре примера умножения, выполненные по способу, живо напоминающему наш народный русский способ. Вот один из них:
Что означает следующее:
9 1 /
18 2
36 4
72 8 /
= 81
Косая черта справа от строки указывает на то, что левое число будет добавлено к результату. Из этого примера видно, что египтяне пользовались приемом умножения, довольно сходным с нашим народным.
При возведении в степень нужно так же делить показатель степени, но вместо удвоения нужно выполнять возведение в квадрат и перемножать квадраты, связанные с нечетными числами. Все операции при этом выполняем по модулю `M`.
function powModM(A:int64; P:longint):longint;
var R:int64;
begin
R:=1;
while p>0 do
begin
if P mod 2=1 then
R:=(R*A) mod M;
A:=(A*A) mod M;
P:=P div 2;
end;
powModM:=R;
end;
Далее нужно найти `N`-е число в последовательности, и `N` может быть очень велико. Для устранения этой сложности воспользуемся принципом Дирихле или "принципом ящиков":
Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.
Все вычисления производятся по модулю `M`, поэтому `A_i` могут принимать только значения от 0 до `M-1`. Среди элементов последовательности с номерами от 0 до `M` существуют элементы `A_i` и `A_j`, такие что `i\ >\ j` и `A_i\ =\ A_j`, так как есть `M+1` элемент и `M` возможных значений. Следующее значение в последовательности зависит только от предыдущего, поэтому `∀\ k≥0` выполняется `A_{i+k}=A_{j+k}`. Т.е. после некоторого `j` последовательность будет повторяться с периодом равным `i-j`.
Чтобы найти `i` и `j`, можно отмечать в специальном массиве, на каком шаге было получено то или иное значение. Затем нужно убрать из `N` все периоды, повторяющиеся целое число раз, для этого нужно найти остаток от деления `N-j` на длину периода `i-j`.
var i,j,A0,B,P,N,M:longint;
step,A:array[0..100000] of longint;
...
for i:=0 to M-1 do
step[i]:=-1;
i:=0;
A[0]:=A0 mod M;
while (i<N) and (step[A[i]]<0) do
begin
step[A[i]]:=i;
A[i+1]:=(powModM(A[i],P)+B) mod M;
inc(i);
end;
if i<N then
begin
j:=step[A[i]];
i:=(N-j) mod (i-j) + j;
end;
writeln(A[i]);
Так как нас интересует только длина периода, то можно не искать начало периодической части, а найти такое `j`, для которого `A_j=A_M`. Длина периода будет равна `M-j`.
A[0]:=A0 mod M;
for i:=1 to M do
A[i]:=(powModM(A[i-1],P)+B) mod M;
if N<=M then
writeln(A[N])
else
begin
j:=M-1;
while A[j]<>A[M] do
dec(j);
writeln(A[(N-j) mod (M-j) + j]);
end;
