|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
Вычисление большой степени числа 6.31.12.2009, 02:49. Показов 4515. Ответов 17
Метки нет (Все метки)
Есть следующая проблема. Нужно возвести число шесть в степень 2500000000 за 1 сек. Ограничения по памяти 5000К. Какие есть идеи ?
0
|
|
(| 31.12.2009, 02:49 | |
|
Ответы с готовыми решениями:
17
Вычисление 2 в степени n Вычисление степени числа и запись цифр степени числа в массив Вычисление факториала и вычисление степени числа |
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
| 31.12.2009, 03:01 | |
|
это называется длинная арифметика в место чисел берутся массивы char в зависимости от грамотности кода будет менятся время компилирования
Добавлено через 8 минут 5000k - 5000kb - 5mb? - места достаточно но проца (на олимпиадные задачки обычно дают от 3 до 6-ти сек) не хватит возможно как вариант использовать BCD 6=3 *2 тобишь можно просто 3 возвести в степень n тем самым ты выиграешь 2 в n операций а потом побитово сместить следующий момент нужно разобрать на кратность 3 9 27 91 ..3 ...9 ..27 и тд..
0
|
|
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
||||||
| 31.12.2009, 03:20 [ТС] | ||||||
|
Да ты что говоришь... длинная арифметика...
 Время выполнения будет в зависить от алгоритма в большей мере. Тут нужна какая - то специальная реализация длинной арифметики. Сначала я думал представить число в виде массива
104166667 умножений. Какие ещё есть мысли ?
0
|
||||||
 
|
|
| 31.12.2009, 12:38 | |
|
Может попробовать возводить много раз в квадрат?..
И еще 6 в такой степени громаднейшее число, уверен, что возводить надо не по модулю??? Кстати зачем тебе unsigned long long ??? Во первых это не стандартная переменная, а во вторых, если говорить про скорость, то сработает только на 64-разрядных машинках.
0
|
|
|
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
| 31.12.2009, 13:19 | |
|
А откуда эта задачка?
0
|
|
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
| 31.12.2009, 13:29 [ТС] | |
|
асm.lviv.ua
Добавлено через 2 минуты To fasked, я уверен, и unsigned long long реализуется на 32 битных машинах x86 в регистрах edx:eax.
0
|
|
|
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
| 31.12.2009, 13:56 | |
|
1. максимальное значение uint64 есть 2^64
2. 6^ 2500000000 это приблизительно 2^(25*(10^8))*2^(25*(10^8))+o(x) 3. 2^(50^(10*8))/2*64 = 50*(10^8)/64 число получится x*10[x>5]*10^7 а 5mb это 5*10^6 и плюс о маленькое от х точно в условии нет ошибки?
0
|
|
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
| 31.12.2009, 13:58 [ТС] | |
|
нету
0
|
|
|
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
| 31.12.2009, 14:15 | |
|
тогда 3 возводи в степень 2,5e9 и побитово смещай на 2,5e9,
кста при реализации умножения uint64 вам нужно будет делать проверку разрядности - при простом умножении в секунду не влезешь на компе с 2,5GHZ
0
|
|
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
| 31.12.2009, 14:23 [ТС] | |
|
Не получиться это уже надо задействовать числа с п.т. и тогда я точно не влезу по времени
Добавлено через 1 минуту упс провтыкал Добавлено через 44 секунды но этот вариант сомневаюсь что прокатит
0
|
|
133 / 132 / 29
Регистрация: 04.01.2009
Сообщений: 415
|
|
| 31.12.2009, 14:33 | |
|
Используй Алгоритм быстрого возведения в степень, а результат записывай в строковый массив.
0
|
|
|
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
|
|
| 31.12.2009, 15:13 | |
|
Можно конкретно номер задачи на Контестере?
0
|
|
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
| 01.01.2010, 18:13 [ТС] | |
|
1245
0
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||
| 02.01.2010, 08:37 | ||
Максимальное значение uint64 есть 2^64-1
0
|
||
|
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
||
| 07.01.2010, 13:57 | ||
0
|
||
Сообщение от pigah
|
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
|
|
| 10.01.2010, 18:31 | |
|
Посмотрел на задачу - сама тема не имеет практической ценности, так как автор решил задачу неверно. У квадратов есть общие стороны - поэтому ответ будет намного меньше.
Самое простое доказание этого - жадником найти ответы для маленьких чисел. Еще проще - посчитать длину ответа (6 в степени 2500000000), это будет 194... словом, почти 2 миллиарда, тоесть 2 гига. Такое не только в лимит памяти, но и в лимит вывода не лезет. Да и за секунду не посчитать, как не старайся.
0
|
|
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
| 14.01.2010, 17:12 [ТС] | |
|
Да, ты прав. Нечего сказать.
Ответ, найден это невозможно.
0
|
|
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
| 14.01.2010, 17:12 | |
|
Помогаю со студенческими работами здесь
18
Вычисление степени числа 3
Вычисление степени числа Напишите программу, осуществляющую заполнение числа типа BigInteger случайными цифрами и вычисление целой степени этого числа Вычисление числа 4 в степени 500 Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
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-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|
Наверх