Вычислить сумму "произведения"

[Rusl92]

финальная версия

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,m:longint;
    t:int64;
    input,output:text;
function power(t:int64;k:integer):int64;
var
res:int64;
Begin
res := 1;
while (k > 0) do
begin
if (k mod 2 = 1) then
res := (res * t) mod m;
t := (t * t) mod m;
k := k div 2;
end;
power := res;
end;
begin
   assign(input,'input.txt');
   reset(input);
   assign(output,'output.txt');
   rewrite(output);
   read(input,n,m);
   t:=power(2,n);
   t:=((n*n-4*n+6) *t-6) mod m;
   write(output,t);
   close(input);
   close(output);

end.

которая все же не работает!

если так не получается - сначала
у меня есть алгоритм возведения числа в степень со сложность o(nlgn)
у меня есть алгоритм нахождения Sn числа
"по модулю" пока забудем

Соответственно S[n] =(n*n-4*n+6)*2^n-6.
это смогу



Ну а это число уже легко посчитать по модулю m.
2^n mod m считаем при помощи быстрого возведения в степень за O(lg n),
а остальное напрямую.


вот этот абзац подробнее можете расписать?

[LeBron]

А самому никак? Действительно, я не даром говорил плохо о гуртках. Может и есть подготовка, но после гуртков нету "занимания программированием".
Попытаюсь объяснить максимально доходчиво. Итак, что сказано в этом абзаце? Для начала посчитаем первое выражение. Быстрое возведение в степень у Вас есть, и ошибки в нем были исправлены еще в одном из первых "финальных вариантов" (возможно, они там есть еще, но я их не вижу, а, так как я вижу другие причины того, что задача не решена, то искать ошибку там нету необходимоти. пока нету). Когда найдем значение, которое соответствует данному выражению, можем подставить его в конечную формулу вместо "куска со степенем". То, что получиться, можно считать и напрямую (Видимо, Дмитрий имел ввиду, что подходит обычная арфметика, без спецалгоритмов, как было с возведением в степень). Но по модулю, что бы не было переполнения.

[Rusl92]

Итак, по порядку
Возведение в степень без переполнение
есть два варианта
I)

function power(a:int64;n1:longint):int64;
var res:int64;
begin
    if odd(n1) then res:=a else res:=1;
    while (n1>1) do
     begin
        n1:=n1 div 2;
        a:=((a*a) mod m);
        if odd(n1) then res:=(res*a) mod m;
     end;
    power:=res;
end;

Верно имхо
II)

function power(t:int64;k:integer):int64;
var
  res:int64;
Begin
  res := 1; 
  while (k > 0) do
   begin
    if (k mod 2 = 1) 
     then
      res := (res * t) mod m;
    t := (t * t) mod m;
    k := k div 2; 
   end; 
   power := res;
end;

тоже похоже на правду

так?

далее когда мы нашли 2^n (Stepen)
мы подставляем в формулу

получаем:

Sn:= ( ( ( (n-4)*n) mod m +6)*Stepen-6) mod m

??

[LeBron]

Сообщение от Rusl92

Итак, по порядку
Возведение в степень без переполнение
есть два варианта
I)


Верно имхо
II)


тоже похоже на правду

так?

Очень похоже, я бы даже сказал - копипастовски похоже. Я всегда юзаю второй. У меня сразу вопрос - чем мы сейчас занимаемся? будем по строке код писать? Как то страшно стало.

[Rusl92]

Sn:= ( ( ( (n-4)*n) mod m +6)*Stepen-6) mod m

так это верно?)

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var n,m:longint;
    t:int64;
    input,output:text;
function power(t:int64;k:integer):int64;
var
res:int64;
Begin
res := 1;
while (k > 0) do
begin
if (k mod 2 = 1) then
res := (res * t) mod m;
t := (t * t) mod m;
k := k div 2;
end;
power := res;
end;
begin
   assign(input,'input.txt');
   reset(input);
   assign(output,'output.txt');
   rewrite(output);
   read(input,n,m);
   t:=power(2,n);
   {по модулю m
    ?
    так различными способами 
    пытался делать
    - не получилось!
    что должно быть тут 
   }

   {t:=((n*n-4*n+6) *t-6) mod m;}
   write(output,t);
   close(input);
   close(output);

end.

Неужели никто кроме librona не знает, как правильно расписать?

[LeBron]

Сообщение от Rusl92

Неужели никто кроме librona не знает, как правильно расписать?

LeBron, lEbron.
Эту задачу даже отгуглить можно - если есть полное условие. Но Вы то его выложили не "на языке оригинала" или "на языке официального перевода". Решение... Хм, как сказать - не уверен, что я сдесь единственный, кто может такое решить. "Если прижмет", то такое под силу многим форумчанинам, хотя этот форум и немного другого уровня/направления. А "делать в свободное время" желающих нету. Отдебажить Ваш код смогут еще больше людей, чем написать с нуля. Только вот почему-то желающих нету.

[Rusl92]

странно очень Lebron
я не прошу написать код, да и не просил

я прошу пояснить до конца алгоритм

то бишь нахождение непосредственно самого Sn-ого
почему так это трудно сделать, что мешает, зачем нужно было так много сообщений, когда можно было сразу НОРМАЛЬНО написать разбор, я не понимаю?

кстати если ввести максимальные данные
то представленный Lebron'ом алгоритм не работает
при n=10^9 и m=1
возникнет переполнение

!

[LeBron]

Алгоритм работает. Странно, как можно тестить авторское решение, не имея рабочего кода. При криворукой реализации - там не переполнение, а немного друкая фишка. Переполнения не может быть в принципе, даже при ограничениях в 2 миллиарда. Алгоритм я объяснил с самого начала. И Вы его поняли. Вернее, не знаю, поняли или нет, но быстренько списали последнюю формулу и побежали сдавать. А если Вы не умеете взять остаток по модулю и даже примерно не ориентируетесь в асимптотических оценках оверфлов-лимитов - это уже совсем другой разговор. Тут надо не алгоритм объяснять, а садиться и учиться программировать.

[Rusl92]

ненавижу вот этого
"тут нада садится и учится программировать"

ну что за дела LeBron
переполнение происходит - и выдается отрицательный результат, я понял это

вот к чему пришел

 t:=power(2,n);
   t:=t mod m;
   v:=((n-4)mod m) *(n mod m);

   t:=((v+6)*t -6) mod m;
   write(output,t);