272. Произведение

Найти произведение чисел a и b.

Вход. Два целых неотрицательных числа a и b (a, b ≤ 10¹⁰⁰⁰⁰), каждое в отдельной строке.

Выход. Вывести одно число, равное произведению a и b.

Пример входа

65536

216

Пример выхода

14155776

РЕШЕНИЕ

преобразование Фурье

Анализ алгоритма

Для нахождения произведения больших чисел с временной оценкой O(log₂n) следует воспользоваться быстрым преобразованием Фурье.

Реализация алгоритма

Определим необходимые константы.

#define PI acos(-1.0)

#define MAX 33000

Реализуем класс для работы с комплексными числами.

struct complex

{

double real, imag;

complex(double _real = 0.0, double _imag = 0.0) : real(_real), imag(_imag){}

};

complex operator +(const complex &a,const complex &b)

{return complex(a.real + b.real ,a.imag + b.imag);}

complex operator -(const complex &a,const complex &b)

{return complex(a.real - b.real, a.imag - b.imag);}

complex operator *(const complex &a,const complex &b)

{return complex(a.real * b.real - a.imag * b.imag,

a.real * b.imag + a.imag * b.real);}

complex operator /(const complex &a,const int &b)

{return complex(a.real / b, a.imag / b);}

complex a[MAX], b[MAX], c[MAX];

int res[MAX], ptr = 0;

Быстрое преобразование Фурье. Если inv = 1, то реализуется обратное преобразование Фурье.

void FFT(complex *a, int n, int inv = 0)

{

int i;

if (n == 1) return;

complex *a0 = new complex[n/2],

*a1 = new complex[n/2];

double angle = 2*PI/n * (inv ? -1 : 1);

complex temp, w(1,0), e = complex(cos(angle),sin(angle));

for(i = 0; i < n / 2; i++)

a0[i] = a[2*i],

a1[i] = a[2*i + 1];

FFT(a0, n >> 1, inv);

FFT(a1, n >> 1, inv);

for(i = 0; i < n / 2; i++)

{

temp = w * a1[i];

a[i] = a0[i] + temp;

a[i+n/2] = a0[i] - temp;

if (inv) a[i] = a[i] / 2, a[i+n/2] = a[i+n/2] / 2;

w = w * e;

}

}

char s[MAX];

int flag = 0;

Основная часть программы. Читаем входные длинные числа и заносим их в массивы a и b в обратном порядке: a[0] содержит цифру единиц, a[1] – цифру десятков и так далее.

gets(s); len1 = (int)strlen(s);

if (s[0] == '0') flag = 1;

for(i = len1 - 1; i >= 0; i--) a[len1 - 1 - i] = s[i] - '0';

gets(s); len2 = (int)strlen(s);

if (s[0] == '0') flag = 1;

for(i = len2 - 1; i >= 0; i--) b[len2 - 1 - i] = s[i] - '0';

Если одно из входных чисел равно нулю, то ответ равен 0.

if (flag)

{

printf("0\n");

return 0;

}

Если len1 и len2 – длины входных чисел, то их произведение содержит не более len1 + len2 цифр. Для запуска преобразования Фурье необходимо, чтобы длины обрабатываемых массивов имели степень двойки. Устанавливаем n равным минимальной степени двойки, для которой n ≥ len1 + len2.

n = 1; while(n < len1 + len2) n <<= 1;

FFT(a,n);

FFT(b,n);

Совершаем умножение многочленов за O(n), которые заданы своими значениями в n точках – корнях n-ой степени из единицы.

for(i = 0; i < n; i++) c[i] = a[i] * b[i];

Выполняем обратное преобразование Фурье для полученного произведения. Переносим ответ из массива комплексных чисел c в массив целых чисел res.

FFT(c,n,1);

for(i = 0; i < n; i++) res[i] = (int)(c[i].real + 0.1);

Нормируем результат. Каждая ячейка массива res должна содержать одну цифру –значение от 0 до 9.

for(i = 0; i < n; i++)

if (res[i] > 9)

{

res[i+1] += res[i] / 10;

res[i] %= 10;

}

Выводим ответ – полученное произведение.

i = n - 1; while(res[i] == 0) i--;

for(; i >= 0; i--) printf("%d",res[i]);

printf("\n");