Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 20 дек 2019, 08:48 
Не в сети
Мастер
Зарегистрирован:
06 окт 2016, 16:35
Сообщений: 298
Cпасибо сказано: 206
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте,

дано выражение:
[math]\left(a*b\right)\%(c+d),[/math]
где [math]\%[/math] - операция нахождения остатка от деления.

[math]1 \le a*b\le 10^{36}, a < (c + d), b < (c+d)[/math]


Вопрос: можно ли как-то раскрыть скобки в этом выражении, причём, так, чтобы раскрылись обе скобки? Необходимо избавиться от прямого умножения [math]a[/math] на [math]b[/math], а также прямого нахождения остатка от деления [math]a[/math] или [math]b[/math] на сумму во вторых скобках.

Вопрос задаю по мотивам решения одной задачи по программированию. Там [math]a[/math] на [math]b[/math] - очень большие числа, прямое умножение которых вызывает в C++ переполнение (рассматриваю решение только через встроенные типы данных и без сторонних библиотек типа boost).

Благодарю за любую помощь.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 01:15 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
Если [math]a[/math] и [math]b[/math] большие числа, а [math]c + d[/math] ещё больше, то без длинной арифметики не обойтись. И нет смысла в "прямом нахождении остатка от деления [math]a[/math] или [math]b[/math] на сумму во вторых скобках", потому что эти остатки и так известны и равны, соответственно, [math]a[/math] и [math]b[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 13:28 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
alekscooper писал(а):
рассматриваю решение только через встроенные типы данных


на плюсах не встроен биг интежер?

Плюс в знаменателе ничего не меняет. задача эквивалентна нахождению [math]ab \mod N[/math].
Есть умножение по Монтгомери, но ваши числа маленькие.
Есть такое соображение:
Если деление на N приходится выполнять часто, можно записать [math]a=a_1\cdot 2^k +a_2, \, b=b_1\cdot 2^k +b_2[/math]
Тогда [math]ab = a_1b_1\cdot 2^{2k}+ (a_1b_2+a_2b_1)2^k +a_2b_2[/math] и заранее предрасчитав [math]2^{2k} \mod N[/math] можно выполнить умножение без переполнения.
Насколько это будет быстрее обычного взятия остатка в арифметике больших чисел (и будет ли), можете узнать сами

Upd. Я только сейчас обратил внимание на размер ваших чисел. У вас встроенный 128-бит тип целых чисел? Уже такой есть?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 15:32 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 5208
Cпасибо сказано: 341
Спасибо получено:
924 раз в 873 сообщениях
Очков репутации: 131

Добавить очки репутацииУменьшить очки репутации
swan
Я так понял, что 64. Но произведение зашкаливает, поэтому ТС хочет как-то по отдельности выполнять операции над сомножителями.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 17:01 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Booker48, это я сегодня весь день такой)) размер произведения, а мне что каждое померещилось

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 18:19 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Выражение:[math]\frac{a b}{(c+d)}[/math] можно представить в виде [math]\frac{a}{e}\frac{b}{f}=\frac{a}{f}\frac{b}{e}[/math] ясно, что [math]c+d=ef[/math]. Так вот, существуют ли условия, которым должны удовлетворять: [math]a,b,c,d,e,f[/math], чтобы остаток от деления [math]\frac{a b}{(c+d)}[/math] , был равен произведению остатков от деления: [math]\frac{a}{e},\frac{b}{f},\frac{a}{f},\frac{b}{e}[/math], исключая нулевые?
Например: [math]a=39,b=42,c=41,d=29,e=2,f=35[/math]
или [math]a=41,b=42,c=41,d=29,e=2,f=35[/math]
или [math]a=37,b=42,c=41,d=29,e=2,f=35[/math]

Должны же быть какие-то соотношения между 4-мя остатками и остатком от всего выражения. Может быть какая-то периодическая зависимость. Только переменных здесь много.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 19:38 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
[math]a=2+35\cdot 2n, 4+35\cdot 2n, 6+35\cdot 2n, 8+35\cdot 2n[/math] при всех тех же остальных значениях. Как будет меняться соотношение остатка от целого выражения с произведениями остатков при изменении a? По-любому здесь какая-то глобальная, многозначная периодичность зарыта.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 20:19 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Можно варьировать не только [math]a[/math], но и [math]b[/math]:
[math]a=43,b=36,c=41,d=29,e=2,f=35[/math]
Все шестерки цифр лежат в рамках этой глобальной периодичности с периодом, равным знаменателю. Это чувствуется интуитивно, но чтобы выявить эту глобальную закономерность, необходимо время, силы, желание и способности.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 23 дек 2019, 13:03 
Не в сети
Последняя инстанция
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1377
Cпасибо сказано: 108
Спасибо получено:
561 раз в 447 сообщениях
Очков репутации: 155

Добавить очки репутацииУменьшить очки репутации
Ну, [math]c+d=r[/math] - с этим ничего не поделаеш. Если проблема только в переполнении при умножении [math]ab[/math], то, в конце концов, можно заменить умножение на сложение. Ведь [math]ab=b+b+\cdots+b[/math]. Сложение, конечно, проводится по модулю [math]r[/math], так что переполнение не будет. Да, будет долго, нерационально, но алгоритм можно улучшить. Например, найти наибольшее [math]k[/math], при котором [math]kb[/math] не дает переполнение, вычислить [math]kb \bmod r[/math] и т.д.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Shadows "Спасибо" сказали:
ivashenko
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 9 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Разложить выражение в ряд Фурье по косинусам

в форуме Ряды Фурье и Интегральные преобразования

bobi228

2

277

23 дек 2020, 12:51

Требуется помощь с нахождением массы пластины

в форуме Интегральное исчисление

Maybeoneday

1

237

10 дек 2014, 19:00

Задача на нахождение остатка

в форуме Теория чисел

MalinkaAmnyam

4

285

04 ноя 2019, 22:03

Задача на нахождение остатка от деления

в форуме Линейная и Абстрактная алгебра

R136a1

7

261

28 ноя 2021, 23:43

Объем остатка жидкости в цисцерне

в форуме Геометрия

Andrey1883

0

542

13 дек 2017, 16:10

Нахождение остатка от деления числа в степени

в форуме Теория чисел

Fjord1

7

2012

21 апр 2015, 12:30

Найдите a и b , при которых многочлен поделится без остатка

в форуме Алгебра

EvusPew

2

167

14 сен 2023, 20:40

В каких числах n деление происходит без остатка?

в форуме Линейная и Абстрактная алгебра

dosya

1

357

15 окт 2015, 20:49

Что-то с суммой

в форуме Тригонометрия

DanyaRRRR

8

445

13 авг 2017, 21:56

Количество трехзначных, с суммой цифр n

в форуме Теория чисел

LookFromBehind

2

477

11 мар 2018, 23:25


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 36


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved