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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 20 дек 2019, 08:48 
Не в сети
Мастер
Зарегистрирован:
06 окт 2016, 16:35
Сообщений: 272
Cпасибо сказано: 189
Спасибо получено:
11 раз в 11 сообщениях
Очков репутации: 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
Сообщений: 2610
Cпасибо сказано: 162
Спасибо получено:
439 раз в 409 сообщениях
Очков репутации: 46

Добавить очки репутацииУменьшить очки репутации
Если [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 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5384
Cпасибо сказано: 83
Спасибо получено:
1157 раз в 1055 сообщениях
Очков репутации: 234

Добавить очки репутацииУменьшить очки репутации
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
Сообщений: 2610
Cпасибо сказано: 162
Спасибо получено:
439 раз в 409 сообщениях
Очков репутации: 46

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как разложить выражение с нахождением остатка и суммой
СообщениеДобавлено: 21 дек 2019, 17:01 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5384
Cпасибо сказано: 83
Спасибо получено:
1157 раз в 1055 сообщениях
Очков репутации: 234

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

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

Добавить очки репутацииУменьшить очки репутации
Выражение:[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
Сообщений: 5051
Cпасибо сказано: 460
Спасибо получено:
375 раз в 352 сообщениях
Очков репутации: 36

Добавить очки репутацииУменьшить очки репутации
[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
Сообщений: 5051
Cпасибо сказано: 460
Спасибо получено:
375 раз в 352 сообщениях
Очков репутации: 36

Добавить очки репутацииУменьшить очки репутации
Можно варьировать не только [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 
Не в сети
Beautiful Mind
Зарегистрирован:
17 окт 2013, 19:46
Сообщений: 1188
Cпасибо сказано: 93
Спасибо получено:
475 раз в 377 сообщениях
Очков репутации: 143

Добавить очки репутацииУменьшить очки репутации
Ну, [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 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Доказать, что выражение делится на 19 без остатка

в форуме Задачи со школьных и студенческих олимпиад

cookybreed

3

1750

26 сен 2012, 18:03

Вычислить выражение с произведением и суммой матриц

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

AGA5510

2

338

04 ноя 2012, 17:35

Как разложить подинтегральное выражение?

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

Noqrax

1

314

04 мар 2012, 22:28

Разложить выражение по формуле бинома Ньютона и упростить

в форуме Комбинаторика и Теория вероятностей

Jackhammer

7

1686

01 ноя 2011, 09:02

Проблема с нахождением минимума функции

в форуме Дифференциальное исчисление

bl_ghost

13

810

04 апр 2013, 16:26

помогите с нахождением площади фигуры

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

jackystorm

1

244

07 май 2012, 12:39

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

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

Maybeoneday

1

191

10 дек 2014, 19:00

проблема с нахождением объема тела вращения по ОY

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

devil_hunter

5

328

30 мар 2014, 13:12

Деление без остатка

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

Tauka

33

1344

03 фев 2014, 03:56

Анализ остатка от деления

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

Vadim LOL

2

475

17 июл 2013, 10:38


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



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

Сейчас этот форум просматривают: searcher и гости: 7


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

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

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

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