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
2014-05-13 18:20:42 Howard Roark
Well, after some timings it is clear that converting a 20,000 digit integer to a base 10 string is about 10-15 times slower than multiplying two 10,000 digit integers in python 3.2.3. So I have a few ideas on how to optimize the conversion.

Last edit: 2013-07-06 02:26:52
2014-05-13 18:20:42 Howard Roark
Interesting; my python 3.2.3 code is too slow using native mult, and my python karatsuba implementation is slower than the native! Time to get smarter I guess to avoid the TLE. Perhaps I'm getting killed by the conversion to base10 for output?

Last edit: 2013-07-04 14:57:53
2014-05-13 18:20:42 Giovanni Botta
Why is java allowed? There's no coding to be doing in java!
2014-05-13 18:20:42 Gurjaspal Singh Bedi
Is bot not supporting .net framework 4.5?
2014-05-13 18:20:42 (Tjandra Satria Gunawan)(曾毅昆)
karatsuba just make your algorithm 2x slower than naive implementation!
Based on my experiment: 1 multiplication + 4 addition is slower than 2 multiplication + 1 addition.
2014-05-13 18:20:42 Gerard Lledó
Just wanted to confirm that this is solvable under one second with an O(N^2) algorithm. No need for Karatsuba...
2014-05-13 18:20:42 anuradha yadav
My Code is working perfectly fine for each test case even the bigger ones. What could be the reason for still getting WA. Please Help :(
2014-05-13 18:20:42 Sumit Khanna
Is Karatsuba the right approach?!?I wrote the code applying karatsuba and it gives correct outputs on ideone,but shows TLE here,,,<snip> ,,here's my code,,smbdy help plz...

Last edit: 2023-05-17 20:50:14
2014-05-13 18:20:42 nishant10
it gave wrong answer when its output r correct to my knowledge please gave some more testcase
2014-05-13 18:20:42 Sandeep Singh Jakhar
nice problem of karatsuba..!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.