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
shiv_1711: 2015-07-17 06:00:45

oh yes!!! Python itself uses karatsuba algo...too easy for python

arcane_achal: 2015-07-05 20:46:56

is it not possible to take large input by gcc compiler??

Yogendra Singh Chouhan: 2015-07-02 12:11:21

In C If I use array to store numbers to be multiplied then I need two array of capacity 10000 and one of 100000000. Is it possible to do so? If not what to do?

Last edit: 2015-07-02 12:11:57
samson_123: 2015-06-15 10:49:54

i have compiled my code in ideone and code blocks the answer is coming correct but when i had submitted in spoj it says wrong answer can anyone help me?

scyth3r: 2015-06-02 05:24:06


Well I applied Karatsuba algorithm in Python…but then I came to know that Python uses O(N^2) grade school multiplication algorithm for small numbers(32-bit numbers), but for big numbers it uses Karatsuba!!!
If you're working in Python either use built-in multiplication operator or go for better optimised algo
PS - Try something new, rather than inclining towards few lines of code :)

Last edit: 2015-06-02 05:53:27
Sunil Kumar Samal: 2015-05-28 17:24:31

it's a 4 line code in pyhton ;)

shuvojit: 2015-05-22 04:51:22

Does input contain negative numbers?

aksam: 2015-05-16 08:07:15

@ViKku mine was 3 line of python code.

ViKku: 2015-04-03 16:07:42

5 lines code in python

:.Mohib.:: 2015-02-23 10:43:50

3 lines in python ;)

Last edit: 2015-05-28 14:14:05

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