Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Доброго времени суток, уважаемые эксперты!
Не могли бы вы мне помочь решить такую задачу:

Вводим n и m
Вычислить Sn такое что
Sn = Сумма k от 0 до n-1 (k^2 * 2^k)

{сумма произведения k в квадрате и 2 в степени k,
где k [0..n-1]}

Ответ вывести по модулю m

Пример:
1) 1 1000 - 0
2) 2 1000 - 2
3) 8 427 - 328

дело в том что n может быть от 0 до 10^9
а m от 1 до 10^9

то есть в данном случае вcтает проблема хранения этого Sn
не могли бы вы сказать, где можно будет хранить такое большое число?
допустим если входные данные будут
10^9 1 - то Sn будет заоблачным

заранее спасибо!

Вопрос задал: Ruslan (статус: 1-ый класс) Вопрос отправлен: 22 ноября 2009, 13:03 Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: Вадим К

Здравствуйте, Ruslan!
Я правильно понимаю, что у Вас нет проблем с собственно расчетом, а есть только проблема в том, как оперировать такими числами? Ведь k^2 * 2^k, если k = 10^9 будет порядка 3*10^8 - то есть, только 300Мб что бы сохранить число в виде цифр:))
Но не все так печально. Тут нам вначале поможет математика. Начнем-с.
- модуль суммы двух числе по m равен сумме модулей этих двух чисел по модулю m, только надо ещё раз взять модуль от суммы (она может быть больше)
то есть, можно складывать не числа, а потом брать модуль. а сразу сложить модули чисел, а потом возможно взять модуль от суммы. А так как нас не интересует всё число, а только модуль, то можно вести расчеты и хранить числа сразу в модулях.
- для модуля произведения работает то же правило.

Итак. приняв вышеприведенные пункты, мы решили проблему больших чисел, их у нас в явном виде уже нет. Но на самом деле одна проблема еще осталась. Это расчет 2^k. Но присмотримся ближе, при расчете каждого слагаемого мы пробегаем от 1 до результата. И если бы мы знали значение 2^(k-1), то рассчитать 2^k очень просто - надо умножить на 2. Что это даст? При классическом расчете время на каждое последующее слагаемое растет в геометрической прогрессии. При новом методе - никакого роста. время стабильно. Итак, имеем все для написания расчета. Для начала напишем новые функции суммы и умножения
(число 10^9 занимает до 31 бита и будет влазить в тип integer. Но вот их сумма будет уже на грани. а произведение - точно выйдет за границы. поэтому я использую int64. Его хватит с запасом, хотя он и чуточку медленее при расчетах)

function summ(a,b,m:int64):Int64;
begin
  result := (a + b) mod m;
end;
 
function mulm(a,b,m:int64):Int64;
begin
  result := (a * b) mod m;
end;

s := 0; //здесь у нас будет сумма
n2 := 1; //здесь у нас будут степени двойки
//поехали
for k:= 0 to n-1 do begin
  //s := (s + k*k*n2);  собственно сума
  s := summ(s + mulm(k, mulm(k,n2,m),m),m);
  //n2 := n2 * 2; рассчет следующей степени двойки для следующего шага.
  n2 := mulm(n2, 2);
end;
//выводим s!

Ответ отправил: Вадим К (статус: Академик) Время отправки: 22 ноября 2009, 15:12

Мини-форум вопроса

Ruslan (статус: 1-ый класс), 22 ноября 2009, 15:19 [#1]: да - это верное решение - но оно не укладывается в секунду!(

Ruslan (статус: 1-ый класс), 22 ноября 2009, 17:43 [#2]: спасибо, вопрос наверное закрыт нашел быстрый алгоритм а он падает на 4 тесте все...

Вадим К (статус: Академик), 22 ноября 2009, 18:15 [#3]: Значит это не быстрый алгоритм. этот алгоритм можно ещё ускорить, заметно ускорить. Галочка "подтверждения прочтения" - вселенское зло.

Егор (статус: 10-ый класс), 22 ноября 2009, 19:53 [#4]: Чуть-чуть подправлю Вадима: для хранения в памяти числа k^2 * 2^k, если k = 10^9 понадобится не 3*10^8 бит, а примерно 10^(3*10^8) бит или около 125*10^(10^8) байт. Если принять ёмкость памяти 64 Гб для одного компьютера (т.е. около 64*10^9), получим что нам нужны примерно 2*10^(10^8-9)=2*10^(99999991) компьютеров. Т.е. для хранения нашего числа не хватит памяти, даже если задействовать ВСЕ компьютеры мира. Опасайтесь багов в приведенном выше коде; я только доказал корректность, но не запускал его. — Donald E. Knuth.

Егор (статус: 10-ый класс), 22 ноября 2009, 20:05 [#5]: Цитата (Вадим К): Конечно, можно функцию расчета чуточку упростить, не вычислять постоянно модуль... не рассчитывать квадраты каждый раз... не пойдёт вообще в цикле считать не надо, потому как простой цикл вида for k:=0 to 1000000000 do // 10^9 begin sum:=(sum + 1) mod m; end; работает даже не секунды, а несколько минут тут уже математиков надо приглашать - для оптимизации не алгоритма, а исходной формулы Опасайтесь багов в приведенном выше коде; я только доказал корректность, но не запускал его. — Donald E. Knuth.

Вадим К (статус: Академик), 22 ноября 2009, 20:24 [#6]: я думал об этом варианте. подозреваю, что тут используется какое то известное (а может и не очень) математическое соотношение. и цикл может быть исключен вообще. Галочка "подтверждения прочтения" - вселенское зло.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.