Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
2 / 2 / 1
Регистрация: 03.11.2014
Сообщений: 129

Быстрое возведение в степень

20.03.2016, 21:16. Показов 2019. Ответов 4
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вот код для быстрого возведения в степень для длинного числа. Можете ткнуть пальцем, где проходит перемножение двух чисел? Заранее спасибо.
C++
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
typedef char byte;
 
class BigInt
{
private:
    vector<byte> digits;
public:
    BigInt() = default;
    BigInt(int num);
 
    BigInt makePow(int power) const;    
    BigInt& operator*=(const BigInt& big);      
 
    friend istream& operator>>(istream& ifs, BigInt& big);      
    friend ostream& operator<<(ostream& ofs, const BigInt& big);    
};
 
 
 
BigInt::BigInt(int num)
{
    for (; num; num /= 10)
        digits.push_back(num % 10);
}
 
istream& operator>>(istream& ifs, BigInt& big)
{
    std::string str;
    ifs >> str;
    big.digits.clear();
    for (int i = str.length() - 1; i >= 0; --i)
        big.digits.push_back(str[i] - '0');
 
    return ifs;
}
 
ostream& operator<<(ostream& ofs, const BigInt& big)
{
    for (int i = big.digits.size() - 1; i >= 0; i--)
        ofs << char(big.digits[i] + '0');
    return ofs;
}
 
BigInt BigInt::makePow(int n) const
{
    BigInt res(1), a(*this);
 
    while (n) {
        if (n & 1)
            res *= a;
        a *= BigInt(a);
        n >>= 1;
    }
    return res;
}
 
BigInt& BigInt::operator*=(const BigInt& two)       //Вроде здесь?
{
    BigInt res(*this);
    int sizeThis = res.digits.size(), sizeTwo = two.digits.size();
    digits = vector<byte>(sizeThis + sizeTwo);
 
    for (int i = 0; i < sizeThis; ++i)
    {
        int r = 0;
        for (int j = 0; j < sizeTwo | r; ++j)
        {
            digits[i + j] += res.digits[i] * (j >= sizeTwo ? 0 : two.digits[j]) + r;
            r = digits[i + j] / 10;
            digits[i + j] -= r * 10;
        }
    }
 
    for (int i = digits.size() - 1; i > 0 && !digits[i]; --i, digits.pop_back());
 
    return *this;
}
 
 
 
int main()
{
    BigInt big;
    int n;
    ifstream ifs("input.txt");
    ofstream ofs("output.txt");
 
    while (ifs) {
        ifs >> big >> n;
        ofs << big.makePow(n) << " ";
        ifs.get();
    }
 
    std::cout << "Sdelano.";
    cin.get();
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
20.03.2016, 21:16
Ответы с готовыми решениями:

Быстрое возведение в степень
Написать функцию быстрого возведения в степень. Функция принимает в качестве параметров y,x и n и возвращает y^x mod y как результат...

Быстрое возведение в степень
Реализуйте алгоритм быстрого возведения в степень для вычисления выражения x = az mod n при целых положительных числах a, z и n. ...

Быстрое возведение в степень
Хочу реализовать быстрое возведение в степень, но проблема в том что то число которое возводим в степень записано не в какой нибудь базовой...

4
 Аватар для meJevin
161 / 153 / 92
Регистрация: 18.11.2015
Сообщений: 677
20.03.2016, 21:21
Скорее строки 51-62, нет? Потому что с 64 строки - реализация оператора присвоения с умножением.
1
Модератор
Эксперт С++
 Аватар для zss
13766 / 10960 / 6490
Регистрация: 18.12.2011
Сообщений: 29,234
20.03.2016, 21:21
57 и 58 строка
Цитата Сообщение от sky123 Посмотреть сообщение
res *= a;
a *= BigInt(a);
1
2 / 2 / 1
Регистрация: 03.11.2014
Сообщений: 129
21.03.2016, 14:35  [ТС]
zss, спасибо большое. А можете подсказать где в классе идет это умножение и как побитово умножаются 2 вектора?
0
 Аватар для meJevin
161 / 153 / 92
Регистрация: 18.11.2015
Сообщений: 677
21.03.2016, 14:54
Цитата Сообщение от sky123 Посмотреть сообщение
как побитово умножаются 2 вектора
Строки 64-84, похоже.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
21.03.2016, 14:54
Помогаю со студенческими работами здесь

Быстрое возведение в степень
Доброго времени суток. Собственно, быстрое возведение в степень: long long fast_pow(long long x, long long y) { int result = 1; ...

Быстрое возведение в степень по mod (остаток от деления)
Доброго времени суток, форумчане! Не могли бы пояснить кусочек кода long long res = 1; while (pow) { if (pow &amp; 1) ...

Вычислить сумму чисел от 1 до N, возведенных в степень M. Возведение в степень оформить как многократное умножение
Не знаю как это написать.. или объясните пожалуйста или помогите сделать)

Возведение в степень!
Возник вопрос - Возможно пока не понятна в чем мысль! Попробую на примере объяснить! Возведение числа 2 в 1000 - ую степень будет...

возведение в степень
помогите плиз! в файле есть задачка. нужно рекурсивно возвести в степень. Код: #include &lt;iostream&gt; float stepen(float a, int n) ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
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 . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru