MUL - Fast Multiplication

Multiply the given numbers.

Input

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.

Output

The results of multiplications.

Example

Input:
5
4 2
123 43
324 342
0 12
9999 12345

Output:
8
5289
110808
0
123437655

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


Added by:Darek Dereniowski
Date:2004-06-01
Time limit:1.649s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:PAL

hide comments
2015-02-04 16:06:10 Vamsi Krishna Avula
try VFMUL after this

Last edit: 2015-02-25 17:19:51
2014-09-07 22:11:31 [Lakshman]
@abdullah malikyar In this problem you have to multiply only two number, But the number can have at most 10000 digits.
2014-09-07 09:00:38 abdullah malikyar
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
2014-08-13 13:45:41 /* Nitin Jaiman */
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
2014-06-04 21:50:15 candide
@jinank jain My peasant multiplication implementation is about 10 times slower than my school-book algorithm implementation.
2014-05-30 10:56:37 sai spoorthy
I HAVE DONE BY KARATSUBA algorithm and used biginteger but it is not accepting my answer can anyone give me some test cases
2014-05-28 01:30:28 candide
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
2014-05-13 18:20:42 [Lakshman]
@Mohit Read the problem statement once again.
the input may contains at most 10000 decimal digits each)
sample try this case
1
100000000000000000000000000000000 999999999999999999999999999999999999999999999999999999999999999
2014-05-13 18:20:42 NOVICE
BigInteger here will give TLE...Refer KARATSUBA algorithm or you can try easier version of this problem(TMUL).
2014-05-13 18:20:42 Saurabh_P
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.