Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

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

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

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

Для умножения длинных чисел используем два массива a и b, а результат умножения запишем в переменную c. Сначала обнулим переменную c, а затем будем производить поциферное умножение: каждую i-ю цифру числа a умножать на каждую j-ю цифру числа b. Тогда результат такого произведения, умноженный на 10i+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 вы можете прочитать здесь.


[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ