VFMUL - Very Fast Multiplication


Multiply the given numbers.

Input

n [the number of multiplications <= 101]

l1 l2 [numbers to multiply (at most 300000 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
sagar_june97p: 2019-01-10 08:04:02

My first FFT problem.

mindrolin: 2018-11-25 13:56:09

If you use Python (both 2 and 3), choose PyPy interpreter if you don't want to get TLE

phoemur: 2018-10-14 04:21:49

In C++, even boost/multiprecision/cpp_int will TLE...

I solved using Fast Fourier Transform Convolution...
But mine is still inefficient with 0.50s runtime.

@rds_98 I don't know if it is OK to put the link here.
Just Google it...

Last edit: 2018-10-14 04:51:14
aneesh_k_14: 2018-08-20 18:54:01

take pi = 3.14159265358979323846

rds_98: 2018-07-28 14:36:30

Can someone Please put his/her solution to Github?

Charlie Yu: 2018-06-07 18:57:04

When you get AC easily with 10 lines of code in Python 3 but can't even past MUL with carefully tailored C++ code you wrote for 5 hours

aditya_rev: 2018-05-06 19:28:20

My 100th, and solved it with PYPY. Not happy at all:"(

mahilewets: 2017-08-25 20:08:31

Use PyPy if you are Python
My Python 3.5 TLE code AC just after changing PyPy interpreter

bnzhaxx: 2017-04-24 23:31:01

And bigInteger is slow slow slow slow slow...

sukanta_27: 2017-04-20 12:59:11

Not even a single person solved this problem in JAVA!!!!


Added by:Darek Dereniowski
Date:2004-11-27
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6
Resource:PAL