Длинное произведение

В данной задаче необходимо реализовать перемножение длинных чисел. Если вы еще не сталкивались с реализацией умножения длинного числа на короткое, то рекомендуем предварительно ознакомиться с решением этой более простой задачи №144 "A*B".

Для умножения длинных чисел используем два массива a и b, а результат умножения запишем в переменную c. Сначала обнулим переменную c, а затем будем производить поциферное умножение: каждую i-ю цифру числа a умножать на каждую j-ю цифру числа b. Тогда результат такого произведения, умноженный на 10^i+j-1 войдет слагаемым в результат умножения, т.е. в c. При этом следует следить, чтобы в переменной c, накапливающей значение произведения не образовывались элементы (цифры), большие 9. Для этого используем переменную cr для хранения значения переноса.

Одно из коротких (но не самых быстрых) решений может быть представлено в виде следующего алгоритма:

  const maxsize=105;
  int a[maxsize], b[maxsize], c[maxsize];
  
  readlong(a);
  readlong(b);

  c=0;
  for i=1..a[0]{
    for j=1..b[0]{
      cr = a[i]*b[j];
      k = i+j-1;
      while(cr>0){
        cr = cr+c[k];
        c[k] = cr mod 10;
        cr = cr div 10;
        if(k>c[0]) c[0]=k;
        k = k+1;
      }
    }
  }

  writelong(c);

Информацию о представлении длинных чисел и реализации функций readlong и writelong вы можете прочитать здесь.

[Обсуждение] [Все попытки] [Задача]