[lxa85]

Lyanni, как обычно, с вас черновики решения, с нас поправки и наводящие вопросы.
БПФ - быстрое преобразование Фурье? С Википедией сверялись?
умножение столбиком - это как должно выглядеть?

[Lyanni]

Алгоритмумножения «в столбик» длинных чисел С = А*В длины n цифр
1) C := 0; (достаточно обнулить n младших цифр)
2) для i = 0 … n-1 выполнить шаги 3-8;
3) d :=0;
4) для j = 0 … n-1 выполнить шаги 3-5;
5) T :=Ci+j + Ai*Bi +d;
6) Ci+j : = LODIGIT(T);
7) d := HIDIGIT(T);
8) Ci+n := d;
9) конец.

БПф - быстрое преобразование фурье
Тогда функция для перемножения двух многочленов будет выглядеть следующим образом:
void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {
vector<base> fa (a.begin(), a.end()), fb (b.begin(), b.end());
size_t n = 1;
while (n < max (a.size(), b.size())) n <<= 1;
n <<= 1;
fa.resize (n), fb.resize (n);

fft (fa, false), fft (fb, false);
for (size_t i=0; i<n; ++i)
fa[i] *= fb[i];
fft (fa, true);

res.resize (n);
for (size_t i=0; i<n; ++i)
res[i] = int (fa[i].real() + 0.5);
функция для перемножения двух длинных чисел практически ничем не отличается от функции для перемножения многочленов. Единственная особенность — что после выполнения умножения чисел как многочлены их следует нормализовать, т.е. выполнить все переносы разрядов:
int carry = 0;
for (size_t i=0; i<n; ++i) {
res[i] += carry;
carry = res[i] / 10;
res[i] %= 10;

Без понятия как это сбить в одну прогу, сама учусь на мат. факе (будущий учитель математики), дали курсовую по такой теме на С++, С++ не проходила...

[Hilaly]

например так:

Код:

cout << "Выберите алгоритм по номеру:" << endl << "1. умножение в столбик" << endl
		<< "2. быстрое преобразование Фурье" << endl << "3. ..." << endl;
int i;
cin >> i;
switch(i)
{
...
}