Вычислить значение выражения

@TermenatorX · Регистрация: 14.02.2013

Студворк — интернет-сервис помощи студентам

Задача такая есть формула, по которой вычисляется ответ. Требуется вывести ответ по модулю 10⁹+7.

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \frac{n^2\cdot (n+1)^2}{4} $

@Puporev · 25.09.2016, 16:14

Почитайте в этой теме, вроде понятно написано, хоть и для С++.
Что означает взятое по модулю 10^9 + 7

@TermenatorX · 25.09.2016, 17:04 **[ТС]**

Я читал, там звучала фраза "каждую операцию делать по модулю", что есть операция в данном случае.

@Puporev · 25.09.2016, 17:06

Ну там же написано

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

в таких задачах ,когда считаете динамику нужно проверять если результат больше или равен 10^9+7 ,то из результата нужно вычитать 10^9+7 пока он не станет меньше

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

надо не вывод делать по модулю, а каждую операцию делать по модулю.

@TermenatorX · 25.09.2016, 17:10 **[ТС]**

Давайте так, я пишу как я себе это представляю а вы говорите правильно это или нет.

@Puporev · 25.09.2016, 17:12

Например по модулю 25.
Получили на какой-то итерации 51. Делаем 51 по модулю 25.

Pascal
1
2
while n>=25 do
n:=n-25;

Добавлено через 56 секунд
Тогда уж пишите полное и точное условие задачи.

@TermenatorX · 25.09.2016, 17:17 **[ТС]**

Pascal
1
2
3
4
5
x:=sqr(n);
x:=x mod 100000007;
x:=x*sqr(n+1);
x:=x mod 100000007;
x:=x div 4;

Добавлено через 2 минуты
https://psv4.vk.me/c810330/u14... vE_aU2z50g

Добавлено через 12 секунд
Вот задача.

Добавлено через 1 минуту
Чуть другая формула, но все же.

@Puporev · 25.09.2016, 17:27

Пишите условие в теме, все равно ссылка не рабочая, да и правилами это запрещено.

@TermenatorX · 25.09.2016, 17:54 **[ТС]**

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

Добавлено через 2 минуты
Условие:
Дано N, найти 1^2+2^2+3^2+4^2+...+N^2.

Добавлено через 1 минуту
А снизу подсказка что это выражение равно
n(n+1)(2n+1)/6

Добавлено через 17 секунд
Вся жизнь обман...

Добавлено через 10 минут
Попробовал в цикле получается TL.

Добавлено через 12 минут
Начну с начала.
Условие:
Дано N, найти 1^2+2^2+3^2+4^2+...+N^2.
Формат выходных данных:
В выходной файл выведите одно число - ответ на задачу. Поскольку ответ может получится довольно большим, то выведите его по модулю 10^9+7.

@TermenatorX · 25.09.2016, 18:07 **[ТС]**

+есть подсказка такая формула:

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \frac{n\cdot (n+1)\cdot (2n+1)}{6} $

@Cyborg Drone · 26.09.2016, 22:35

Договоримся использовать целые числа, а именно, типа longint. Слегка преобразуем выражение:

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \frac{n^2\cdot (n+1)^2}{4}=\frac{n^2\cdot (n+1)^2}{2^2} $

Теперь, если n чётное, будем использовать

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \left( \frac{n}{2}\right)^2\cdot (n+1)^2 $

, а если нечётное,

$https://www.cyberforum.ru/cgi-bin/latex.cgi? n^2\cdot \left( \frac{n+1}{2}\right)^2 $

Это для того, чтобы остаться в целых числах, избавиться от деления в циклах и уменьшить количество итераций.

Обзовём выражение под первым квадратом n, под вторым - n₁, какие бы они там не получились в зависимости от приведённых выше формул. И избавимся от операции возведения в степень.

$https://www.cyberforum.ru/cgi-bin/latex.cgi? n^2n_1^2=(nn)(n_1n_1) $

С умножением по модулю всё очень плохо, при всех ухищрениях n никак не сможет быть более 308 (навскидку для longint). Поэтому умножение по модулю будем делать с помощью сложения по модулю (столбиком, как в школе учили).
Тогда n вполне может быть не более 2³¹-2=2147483646 (для типа longint).
Вместо n будем использовать |n|, чтобы цикл для всех умножений был однотипным, всё равно имеет место возведение в квадрат.

В результате вытанцовывается вот такая программа:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const m = 1000000007;
function mmm(x, y: longint): longint;
var p, t: longint;
begin
  t := x mod m;
  p := 0;
  while y > 0 do
    begin
      if odd(y) then p := (p + t) mod m; //Вариант: if y mod 2 = 1 ... if y and 1 = 1 ...
      t := (t + t) mod m;
      y := y shr 1 //Вариант: y := y div 2
    end;
  mmm := p
end;
var n, n1: longint;
begin
  write('n = ');
  readln(n);
  n := abs(n);
  n1 := n + 1;
  if odd(n) then n1 := n1 div 2 else n := n div 2;
  writeln('n^2*(n+1)^2/4 mod ', m, ' = ', mmm(mmm(n, n), mmm(n1, n1)));
  readln
end.

При больших n не слишком прыткая программа, но... Что делать... Такова се ля ва.

@TermenatorX · 27.09.2016, 20:07 **[ТС]**

Не по теме:

Тавтология получается и в конце и.

Добавлено через 2 минуты
Если все же се ля ва, то тогда хотя бы таково C'est La Vie''во французском языке среднего рода....

@Cyborg Drone · 29.09.2016, 23:06

Не по теме:

TermenatorX, да бог с нею, тавтологией, зато в рифму... Да и какой с меня спрос - я же французский язык цурюк ферштеен совершенно...

@TermenatorX · 30.09.2016, 22:24 **[ТС]**

Можно вопрос как работает это умножение:

Pascal
2
3
4
5
6
7
8
9
10
11
12
13
14
function mmm(x, y: longint): longint;
var p, t: longint;
begin
  t := x mod m;
  p := 0;
  while y > 0 do
    begin
      if odd(y) then p := (p + t) mod m; //Вариант: if y mod 2 = 1 ... if y and 1 = 1 ...
      t := (t + t) mod m;
      y := y shr 1 //Вариант: y := y div 2
    end;
  mmm := p
end;

Добавлено через 2 часа 4 минуты
Cyborg Drone, Прошлая программа прошла тесты, для второй программы формула такая $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n(n+1)(2n+1)}{6}$
Я переписал, но программа проходит не все тесты,подскажите что не учел.

Pascal
1
2
3
if odd(n) then
  writeln(mmm(mmm(n,(n+1) div 2),(mmm(2,n)+1)) div 3)
  else writeln(mmm(mmm(n div 2,n+1),(mmm(2,n)+1)) div 3);

@Cyborg Drone · 01.10.2016, 02:50

Обычное умножение в столбик, но по модулю. Обычное умножение в двоичной форме (пример):

∙∙∙∙∙∙∙1011000
∙∙∙∙∙∙*1100111
--------------
∙∙∙∙∙∙∙1011000
∙∙∙∙∙+10110000
∙∙∙∙+101100000
∙∙∙+0000000000
∙∙+00000000000
∙+101100000000
+1011000000000
--------------
10001101101000

Серым цветом изображены нули, которые мы в школе не писали, но которые, тем не менее, имеют место быть.

Нетрудно заметить, что:

Если соответствующий разряд второго сомножителя равен единице, очередное слагаемое равно первому сомножителю, сдвинутому влево на количество позиций, соответствующее номеру (к примеру, k) разряда второго сомножителя, на который в данный момент умножается первый сомножитель, если считать, что младший разряд имеет номер 0. Ну, или, что то же самое, равно первому сомножителю, умноженному на 2^k.

Если соответствующий разряд второго сомножителя равен нулю, очередное слагаемое равно нулю (точнее, нулю, сдвинутому на k разрядов).

Пока что всё как в школе, но в двоичной форме.

Умножение в двоичной форме по модулю (для простоты рассуждений пусть будет m = 10000000₂, в этом случае деление можно заменить "обрезкой" числа до 7 разрядов):

∙∙∙∙∙∙∙1011000
∙∙∙∙∙∙*1100111
--------------
∙∙∙∙∙∙∙1011000
∙∙∙∙∙+10110000
∙∙∙∙+101100000
∙∙∙+0000000000
∙∙+00000000000
∙+101100000000
+1011000000000
--------------
10001101101000

Красным цветом изображены разряды, которые при операции деления по модулю просто-напросто пропадают. Хорошо видно, что на любом этапе вычислений любое число обязательно меньше, чем m. И вот что интересно: можно всё перемножить, "как обычно", а затем результат разделить по модулю на m, а можно и все сомножители, промежуточные слагаемые и результат делить по модулю на m в процессе вычислений, результат от этого не изменится. Зато не будет переполнения в процессе вычислений.

С теорией вроде всё, что неясно, пишите. Комментарии к коду функции:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const m = 1000000007;
function mmm(x, y: longint): longint;
var p, t: longint;
begin
  t := x mod m; //текущее слагаемое, "обрезанный" и сдвинутый влево
                //(ладно, пока ещё не сдвинутый) первый сомножитель
  p := 0; //переменная для результата, сюда будем прибавлять 
          //очередное сдвинутое слагаемое
  while y > 0 //второй сомножитель будем сдвигать вправо, 
              //пока он не станет равным 0, для того, чтобы разряд, 
              //на который умножаем, всегда был номер 0
              //иными словами, окончание цикла - тогда, когда будут 
              //использованы все значащие разряды второго сомножителя
    begin
      if odd(y) then p := (p + t) mod m; //если очередной разряд равен 1, 
                                         //прибавляем к произведению 
                                         //сдвинутый первый сомножитель,
                                         //естественно, тут же "обрезаем"
      t := (t + t) mod m; //готовим следующее слагаемое: сдвигаем t влево
                          //на 1 разряд, ну и, "обрезаем", куда ж денешься
      y := y shr 1 //сдвигаем второй сомножитель вправо, при этом младший разряд 
                   //(номер 0) теряется, а очередной разряд встаёт на место младшего
    end;
  mmm := p //возвращаемое значение функции, произведение по модулю mmm = (x * y) mod m
end;

Здесь под обрезкой имеется ввиду mod m. Вроде всё. Можете для интереса протестировать программу при малом n, таком, чтобы результат не превысил m. Результат в этом случае можно проверить с помощью калькулятора.

Добавлено через 4 часа 24 минуты

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

подскажите что не учел

Все варианты не учли. Допустим, n = 5. Ну и... 2n + 1 = 11, на 3 никак не делится. Тут всё несколько сложнее.

Сначала докажем, что n(n+1)(2n+1) всегда делится на шесть. Для этого умножим числитель и знаменатель на 4.

$https://www.cyberforum.ru/cgi-bin/latex.cgi? \frac{n(n+1)(2n+1)}{6}=\frac{4n(n+1)(2n+1)}{4\cdot 6}=\frac{2n(2n+1)(2n+2)}{2\cdot 3\cdot 4} $

Рассмотрим последнее частное. В числителе получилось три подряд идущих натуральных числа, следовательно, одно из них обязательно имеет делитель три. 2n и 2n+2 - два соседних чётных числа, следовательно, одно из них имеет делитель 4, а другое имеет делитель 2. Но исходное частное есть ни что иное, как сокращённое на 4 последнее частное. Следовательно, одно из трёх чисел делится на 3, а одно из двух первых чисел, поскольку 2n+1 обязательно нечётное, делится на 2. И это не обязательно разные числа, например, при n=5 делится на 3 и на 2 одно и то же число: n+1.

Теперь насчёт 2n+1. Не следует умножать n на 2 с помощью функции, затем складывать с 1 и делить на 3, если вдруг такое надо будет сделать. Если n>500000003, то один (старший) двоичный разряд будет утерян, и результат деления будет неверным. Так что 2n+1 придётся вычислять непосредственно. Но как это сделать, чтобы не возникло переполнения? Небольшие преобразования:

2n+1=n+n+1=(n-1)+(n-1)+3

Последнее число, то есть, 3, явно делится на 3. Так как всё число 2n+1 делится на 3, то и 2n+1-3=2n-2 делится на 3, но 2n-2 чётное, значит, и (2n-2)/2=n-1 делится на 3. Получается, что (2n+1) div 3=((n-1) div 3)*2+1.

Если 2n+1 не делится на 3, то тогда его можно будет вычислить с помощью функции mmm, потеря старших разрядов будет связана только с mod m, то есть, соответствующая заданию.

Пусть n=n, n1=n+1, n2=2n+1

Теперь соединяем это всё воедино и пишем вызывающую программу:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var n, n1, n2: longint;
begin
  write('n = ');
  readln(n);
  n := abs(n);
  n1 := n + 1;
  if odd(n) 
    then n1 := n1 div 2 
    else n := n div 2;
  if (n mod 3 <> 0) and (n1 mod 3 <> 0) 
    then n2 := ((n - 1) div 3) * 2 + 1 
    else begin
      n2 := mmm(n, 2) + 1; //именно (n, 2), не наоборот, для скорости и чтобы не было переполнения. mod m здесь не нужно
      if n mod 3 = 0
        then n := n div 3
        else n1 := n1 div 3
    end;
  writeln(mmm(mmm(n2, n1), n)) //n2 самая первая, в функции её как раз ждёт x mod m
end.

@TermenatorX · 01.10.2016, 17:05 **[ТС]**

Не по теме:

Можно вопрос вам самому интересно задачи решать или у вас иная высшая цель?

Добавлено через 15 минут
У меня вопрос: как вы перешли от двоичного представления к десятеричному?

Ураааа, я решил.
Такие как вы делают мир лучше.

then n2 := ((n - 1) div 3) * 2 + 1
n2 := mmm(n, 2) + 1;
Вот здесь нужно начальное значение N.

Добавлено через 1 минуту
Программа выглядит так:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const m = 1000000007;
function mmm(x, y: longint): longint;
var p, t: longint;
begin
  t := x mod m; //текущее слагаемое, "обрезанный" и сдвинутый влево
                //(ладно, пока ещё не сдвинутый) первый сомножитель
  p := 0; //переменная для результата, сюда будем прибавлять 
          //очередное сдвинутое слагаемое
  while y > 0 //второй сомножитель будем сдвигать вправо, 
              //пока он не станет равным 0, для того, чтобы разряд, 
              //на который умножаем, всегда был номер 0
              //иными словами, окончание цикла - тогда, когда будут 
              //использованы все значащие разряды второго сомножителя
    begin
      if odd(y) then p := (p + t) mod m; //если очередной разряд равен 1, 
                                         //прибавляем к произведению 
                                         //сдвинутый первый сомножитель,
                                         //естественно, тут же "обрезаем"
      t := (t + t) mod m; //готовим следующее слагаемое: сдвигаем t влево
                          //на 1 разряд, ну и, "обрезаем", куда ж денешься
      y := y shr 1 //сдвигаем второй сомножитель вправо, при этом младший разряд 
                   //(номер 0) теряется, а очередной разряд встаёт на место младшего
    end;
  mmm := p //возвращаемое значение функции, произведение по модулю mmm = (x * y) mod m
end;
var n, n1, n2, nd: longint;
begin
  write('n = ');
  readln(n);
  n := abs(n);
  nd := n;
  n1 := n + 1;
  if odd(n) 
    then n1 := n1 div 2 
    else n := n div 2;
  if (n mod 3 <> 0) and (n1 mod 3 <> 0) 
    then n2 := ((nd - 1) div 3) * 2 + 1 
    else begin
      n2 := mmm(nd, 2) + 1; //именно (n, 2), не наоборот, для скорости и чтобы не было переполнения. mod m здесь не нужно
      if n mod 3 = 0
        then n := n div 3
        else n1 := n1 div 3
    end;
  writeln(mmm(mmm(n2, n1), n)) //n2 самая первая, в функции её как раз ждёт x mod m
end.

@Cyborg Drone · 03.10.2016, 22:24

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

Не по теме:

...или у вас иная высшая цель?

Не по теме:

Я не знаю. Интересные задачи мне решать интересно. Тому, кто стремится что-то сделать, не грех и помочь.

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

как вы перешли от двоичного представления к десятеричному?

Никак. Числа в компьютере в большинстве случаев в двоичном представлении, это встроенные процедуры и функции языков высокого уровня их вводят/выводят в десятичной форме. А в примере умножал в двоичной форме (столбиком) с целью показать, как сделано умножение в функции mmm.

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@TermenatorX 2 / 2 / 0 Регистрация: 14.02.2013 Сообщений: 145

	Вычислить значение выражения 25.09.2016, 15:42. Показов 3435. Ответов 16 Метки нет (Все метки) Задача такая есть формула, по которой вычисляется ответ. Требуется вывести ответ по модулю 10⁹+7. $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> \frac{n^2\cdot (n+1)^2}{4}<br />$ 0

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	25.09.2016, 16:14
	Почитайте в этой теме, вроде понятно написано, хоть и для С++. Что означает взятое по модулю 10^9 + 7 1

@TermenatorX 2 / 2 / 0 Регистрация: 14.02.2013 Сообщений: 145
	25.09.2016, 17:04 [ТС]
	Я читал, там звучала фраза "каждую операцию делать по модулю", что есть операция в данном случае. 0

@TermenatorX 2 / 2 / 0 Регистрация: 14.02.2013 Сообщений: 145
	25.09.2016, 17:10 [ТС]
	Давайте так, я пишу как я себе это представляю а вы говорите правильно это или нет. 0

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	25.09.2016, 17:27
	Пишите условие в теме, все равно ссылка не рабочая, да и правилами это запрещено. 1

@TermenatorX 2 / 2 / 0 Регистрация: 14.02.2013 Сообщений: 145
	25.09.2016, 17:54 [ТС]
	А я понял, не стоит решать задачу по подсказке. Добавлено через 2 минуты Условие: Дано N, найти 1^2+2^2+3^2+4^2+...+N^2. Добавлено через 1 минуту А снизу подсказка что это выражение равно n(n+1)(2n+1)/6 Добавлено через 17 секунд Вся жизнь обман... Добавлено через 10 минут Попробовал в цикле получается TL. Добавлено через 12 минут Начну с начала. Условие: Дано N, найти 1^2+2^2+3^2+4^2+...+N^2. Формат выходных данных: В выходной файл выведите одно число - ответ на задачу. Поскольку ответ может получится довольно большим, то выведите его по модулю 10^9+7. 0

@TermenatorX 2 / 2 / 0 Регистрация: 14.02.2013 Сообщений: 145
	25.09.2016, 18:07 [ТС]
	+есть подсказка такая формула: $https://www.cyberforum.ru/cgi-bin/latex.cgi?<br /> \frac{n\cdot (n+1)\cdot (2n+1)}{6}<br />$ 0

@TermenatorX
	27.09.2016, 20:07 [ТС]
	Не по теме: Тавтология получается и в конце и. Добавлено через 2 минуты Если все же се ля ва, то тогда хотя бы таково C'est La Vie''во французском языке среднего рода.... 0

@Cyborg Drone
	29.09.2016, 23:06
	Не по теме: TermenatorX, да бог с нею, тавтологией, зато в рифму... Да и какой с меня спрос - я же французский язык цурюк ферштеен совершенно... 0

Вычислить значение выражения

Решение