MUL - Fast Multiplication

Multiply the given numbers.


n [the number of multiplications <= 1000]

l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Text grouped in [ ] does not appear in the input file.


The results of multiplications.


4 2
123 43
324 342
0 12
9999 12345


Warning: large Input/Output data, be careful with certain languages

hide comments
Vamsi Krishna Avula: 2015-02-04 16:06:10

try VFMUL after this

Last edit: 2015-02-25 17:19:51
[Lakshman]: 2014-09-07 22:11:31

@abdullah malikyar In this problem you have to multiply only two number, But the number can have at most 10000 digits.

abdullah malikyar: 2014-09-07 09:00:38

Do they mean they have only 2 numbers(100 10) to multiply or they can have multiple numbers (2 10 200 100) aswell? and i did implement it using my own algorithm and ran all the test cases the output was correct but when i submit my code here in SPOJ it says wrong answer can anyone explain how?

Last edit: 2014-09-07 09:17:28
/* Nitin Jaiman */: 2014-08-13 13:45:41

I implemented Karatsuba it was giving me tle for "Not SO Fast Multiplication " which means it was taking more than 12 sec. I implemented the same algo in c++ it took only 1.2 secs. In short JAVA SUCKS

re(vamsi): I don't code in Java but Java contains bigint library right?

Last edit: 2015-01-31 13:31:09
candide: 2014-06-04 21:50:15

@jinank jain My peasant multiplication implementation is about 10 times slower than my school-book algorithm implementation.

sai spoorthy: 2014-05-30 10:56:37

I HAVE DONE BY KARATSUBA algorithm and used biginteger but it is not accepting my answer can anyone give me some test cases

candide: 2014-05-28 01:30:28

EDIT 2015/05
AC in 0.09s with the grammar-school method with 10^8 base. Don't mimic the method too closely : carry as late as possible in order to minimize long long divisions (expensive). No trick with I/O. Learned a lot.

AC in 0.00s with Karatsuba algorithm. Hybrid with classical multiplication (otherwise Karatsuba is slower).

Last edit: 2015-05-03 21:29:18
[Lakshman]: 2014-05-13 18:20:42

@Mohit Read the problem statement once again.
the input may contains at most 10000 decimal digits each)
sample try this case
100000000000000000000000000000000 999999999999999999999999999999999999999999999999999999999999999

NOVICE: 2014-05-13 18:20:42

BigInteger here will give TLE...Refer KARATSUBA algorithm or you can try easier version of this problem(TMUL).

Saurabh_P: 2014-05-13 18:20:42

I tried it using BigIntegr data-type in java and it is showing me compilation error here.

Last edit: 2013-12-26 00:13:11

Added by:Darek Dereniowski
Time limit:1.649s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)