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


hide comments
Howard Roark: 2014-05-13 18:20:42

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
Howard Roark: 2014-05-13 18:20:42

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
Giovanni Botta: 2014-05-13 18:20:42

Why is java allowed? There's no coding to be doing in java!

Gurjaspal Singh Bedi: 2014-05-13 18:20:42

Is bot not supporting .net framework 4.5?

(Tjandra Satria Gunawan)(曾毅昆): 2014-05-13 18:20:42

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.

Gerard Lledó: 2014-05-13 18:20:42

Just wanted to confirm that this is solvable under one second with an O(N^2) algorithm. No need for Karatsuba...

anuradha yadav: 2014-05-13 18:20:42

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 :(

Sumit Khanna: 2014-05-13 18:20:42

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
nishant10: 2014-05-13 18:20:42

it gave wrong answer when its output r correct to my knowledge please gave some more testcase

Sandeep Singh Jakhar: 2014-05-13 18:20:42

nice problem of karatsuba..!!


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