Форум программистов, компьютерный форум CyberForum.ru

Быстрое умножение длинных чисел. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Почему нет реакции от DllMain? http://www.cyberforum.ru/cpp-beginners/thread158517.html
Доброго времени суток! Начал изучать dll, и возникла такая проблема - библиотека загружается, функции экспортируются. А вот DLL_PROCESS_ATTACH не срабатывает, как и остальные(DLL_PROCESS_DETACH, DLL_THREAD_ATTACH...) BOOL APIENTRY DllMain (HINSTANCE hInst /* Library instance handle. */ , DWORD reason /* Reason this function is being called. */ , ...
C++ Как перевести double в char? как перевести double в char? http://www.cyberforum.ru/cpp-beginners/thread158481.html
есть массив char. есть строка string. как присвоить значению string-a значение char-a? C++
есть массив char. есть строка string. как присвоить значению string-a значение char-a?
Открытие проекта в ERS 2010 C++
Здравствуйте. Как сделать так, чтобы при открытии проекта (Ctrl+F11) открывались и исходники данного проекта? При открытии проекта так и остаюсь на "Welcome Page", после открытия нужно открывать каждый исходник по отдельности через Open. Что нужно настроить?
C++ Использование strcpy_s http://www.cyberforum.ru/cpp-beginners/thread158453.html
Добрый день. Словил странную проблему (компилятор MVS2010) #include<iostream> #include<cstring> using namespace std; class String { private: char *stroka; public:
C++ Игра Лягушка Вот собственно игра заключается в том чтобы перевести человечка на другую сторону дороги 5 полос по которым ездят машины с разными скоростями * - игрок > - машина Проблема в том что я не могу сделать так чтобы когда перемещаешь игрока двигалась и машина, начинаешь двигать игрока машина встаёт и не двигается. Кто то мне сказал что нужно функцию с временем какую то использовать я вообще не... подробнее

Показать сообщение отдельно
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.08.2010, 18:53     Быстрое умножение длинных чисел.
В общем вопрос стоит так: где можно найти красивый код на агоритм Карацубы. В часности - http://acm.tju.edu.cn/toj/vcontest/showp6506_I.html - это задача, на которой я все время получаю вронги, вот код:
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
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <ctime>
 
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
#define MIN(a,b) ( (a) < (b) ? a : b )
#define MAX(a,b) ( (a) > (b) ? a : b )
#define ABS(a) ( (a) < 0 ? -(a) : a )
#define ALL(a) a.begin(), a.end()
 
const LL base = 1000*1000*1000;
 
VI operator * (const VI &a, VI b){
    VI res(a.size() + b.size());
    for (int i = 0; i < a.size(); ++i){
        for(int j = 0, carry = 0; j < b.size() || carry; ++j){
            if (j == b.size()) b.push_back(0);
            LL cur = carry + res[i+j] + a[i] * 1ll * b[j];
            res[i+j] = cur % base;
            carry = cur / base;
        }
    }
    while (!res.back() && res.size() > 1) res.pop_back();
    return res;
}
template <class T1, class T2>
T1 operator *= (T1 &a, const T2 &b){
    return a = a * b;
}
VI BinPow(const int &a, int n){
    VI res(1,1), b(1,a % base);
    if (a / base) b.push_back(a / base);
    while (n) if (n & 1) res *= b, --n; else n >>= 1, b *= b;
    return res;
}
ostream &operator << (ostream &out, const VI &a){
    string res = "", d;
    stringstream tmp;
    tmp << a.back();
    tmp >> d; res += d; tmp.clear();
    for(int i = a.size()-2; i > -1; --i){
        tmp << setw(7) << setfill('0') << a[i];
        tmp >> d; res += d; tmp.clear();
    }
    d = "";
    FOR(i,0,res.size()) {d += res.substr(i,70) + (i + 69 < res.size() ? "\n" : ""); i += 69;}
    out << d;
    return out;
}
 
int main(){
    int a, n;
    cin >> a >> n;
    cout << BinPow(a,n);
    return 0;
}
Добавлено через 7 минут
Все, получил Accepted. Ошибка была в количестве символов, если число 0 я выводил 7 цыфер вместо 9 Частный вопрос снят, остался общий: как красиво закодить алгоритм Карацуба?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 05:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru