A*B
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
В данной задаче требуется умножить длинное число на короткое. Когда мы делаем подобное вручную, то мы умножаем на короткое число поразрядно (т.е. поциферно), но при программной реализации мы можем число А умножать на B так же, как если бы B состояло всего из одной цифры. В процессе умножения результат будем записывать сразу в имеющийся массив a, а значение переноса в переменную c.
Приведем один из алгоритмов решения данной задачи:
const maxsize=105;
int a[maxsize], b, c=0;
readlong(a);
read(b);
for i=1..a[0]{
a[i] = a[i]*b+c;
c = a[i] div 10;
a[i] = a[i] mod 10;
}
while(c>0){
a[0] = a[0]+1;
a[a[0]] = c mod 10;
c = c div 10;
}
writelong(a);
Информацию о представлении длинных чисел и реализации функций readlong и writelong вы можете прочитать здесь.
|