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

@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.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

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

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

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	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 Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	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

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

Решение