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
|
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