Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 9 ] |
|
Автор | Сообщение | |
---|---|---|
alekscooper |
|
|
дано выражение: [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). Благодарю за любую помощь. |
||
Вернуться к началу | ||
Booker48 |
|
|
Если [math]a[/math] и [math]b[/math] большие числа, а [math]c + d[/math] ещё больше, то без длинной арифметики не обойтись. И нет смысла в "прямом нахождении остатка от деления [math]a[/math] или [math]b[/math] на сумму во вторых скобках", потому что эти остатки и так известны и равны, соответственно, [math]a[/math] и [math]b[/math].
|
||
Вернуться к началу | ||
swan |
|
|
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-бит тип целых чисел? Уже такой есть? |
||
Вернуться к началу | ||
Booker48 |
|
|
swan
Я так понял, что 64. Но произведение зашкаливает, поэтому ТС хочет как-то по отдельности выполнять операции над сомножителями. |
||
Вернуться к началу | ||
swan |
|
|
Booker48, это я сегодня весь день такой)) размер произведения, а мне что каждое померещилось
|
||
Вернуться к началу | ||
ivashenko |
|
|
Выражение:[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-мя остатками и остатком от всего выражения. Может быть какая-то периодическая зависимость. Только переменных здесь много. |
||
Вернуться к началу | ||
ivashenko |
|
|
[math]a=2+35\cdot 2n, 4+35\cdot 2n, 6+35\cdot 2n, 8+35\cdot 2n[/math] при всех тех же остальных значениях. Как будет меняться соотношение остатка от целого выражения с произведениями остатков при изменении a? По-любому здесь какая-то глобальная, многозначная периодичность зарыта.
|
||
Вернуться к началу | ||
ivashenko |
|
|
Можно варьировать не только [math]a[/math], но и [math]b[/math]:
[math]a=43,b=36,c=41,d=29,e=2,f=35[/math] Все шестерки цифр лежат в рамках этой глобальной периодичности с периодом, равным знаменателю. Это чувствуется интуитивно, но чтобы выявить эту глобальную закономерность, необходимо время, силы, желание и способности. |
||
Вернуться к началу | ||
Shadows |
|
|
Ну, [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] и т.д.
|
||
Вернуться к началу | ||
За это сообщение пользователю Shadows "Спасибо" сказали: ivashenko |
||
[ Сообщений: 9 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Разложить выражение в ряд Фурье по косинусам | 2 |
277 |
23 дек 2020, 12:51 |
|
Требуется помощь с нахождением массы пластины
в форуме Интегральное исчисление |
1 |
237 |
10 дек 2014, 19:00 |
|
Задача на нахождение остатка
в форуме Теория чисел |
4 |
285 |
04 ноя 2019, 22:03 |
|
Задача на нахождение остатка от деления
в форуме Линейная и Абстрактная алгебра |
7 |
261 |
28 ноя 2021, 23:43 |
|
Объем остатка жидкости в цисцерне
в форуме Геометрия |
0 |
542 |
13 дек 2017, 16:10 |
|
Нахождение остатка от деления числа в степени
в форуме Теория чисел |
7 |
2012 |
21 апр 2015, 12:30 |
|
Найдите a и b , при которых многочлен поделится без остатка
в форуме Алгебра |
2 |
167 |
14 сен 2023, 20:40 |
|
В каких числах n деление происходит без остатка?
в форуме Линейная и Абстрактная алгебра |
1 |
357 |
15 окт 2015, 20:49 |
|
Что-то с суммой
в форуме Тригонометрия |
8 |
445 |
13 авг 2017, 21:56 |
|
Количество трехзначных, с суммой цифр n
в форуме Теория чисел |
2 |
477 |
11 мар 2018, 23:25 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 36 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |