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
|
candide:
2014-06-02 00:01:18
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 |
|
Naman Goyal:
2014-05-24 14:05:34
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? |
|
Roman Sol:
2014-05-13 18:20:59
Is it possible to solve it with Schönhage–Strassen? It requires binary representation of digits not decimal. |
|
Emir Habul:
2014-05-13 18:20:59
Try problems MUL and TMUL first.
|
|
[Rampage] Blue.Mary:
2014-05-13 18:20:59
NTT can get Accepted too. |
|
Brian Bi:
2014-05-13 18:20:59
Longer numbers don't demand higher precision? |
|
[Trichromatic] XilinX:
2014-05-13 18:20:59
FFT (using double) CAN get Accepted. |
| 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 |
RSS