| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
||||||
|
2014-06-02 00:01:18 candide
Karatsuba (with base 10^7 and using long long) implemented with a little care can get AC in 0.32s. Little care means : carry as late as possible in order to minimize divisions, no zero padding, hybrid with school division. I/O are not a problem here. Last edit: 2016-04-29 09:29:09 |
||||||
|
2014-05-24 14:05:34 Naman Goyal
Karatsuba with base 10^8 is getting TLE (which was getting AC for MUL). Can anyone give any leads as which FFT algorithm I should try to implement? |
||||||
|
2014-05-13 18:20:59 Roman Sol
Is it possible to solve it with Schönhage–Strassen? It requires binary representation of digits not decimal. |
||||||
|
2014-05-13 18:20:59 Emir Habul
Try problems MUL and TMUL first. They are easier version of this. |
||||||
|
2014-05-13 18:20:59 [Rampage] Blue.Mary
NTT can get Accepted too. |
||||||
|
2014-05-13 18:20:59 Brian Bi
Longer numbers don't demand higher precision? |
||||||
|
2014-05-13 18:20:59 [Trichromatic] XilinX
FFT (using double) CAN get Accepted. |
||||||
RSS