Начало
Соревнования
Разбор задачи 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
XP 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, поэтому Ai могут принимать только значения от 0 до M-1. Среди элементов последовательности с номерами от 0 до M существуют элементы Ai и Aj, такие что i > j и Ai = Aj, так как есть M+1 элемент и M возможных значений. Следующее значение в последовательности зависит только от предыдущего, поэтому ∀ k≥0 выполняется Ai+k=Aj+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, для которого Aj=AM. Длина периода будет равна 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;
