| Submit | All submissions | Best solutions | Back to list |
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 |
||||||||||||||
RSS