Submit solution
Points:
20 (partial)
Time limit:
1.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
Brain****, C, C++, Pascal, Rust
For a while now, show off demonstrate his fast multiplication code, has created a problem that really tests the accuracy and speed of your fast multiplication code.
Input Specification
The first line of input will have .
The second line of input will have .
Both and
will be non-negative integers strictly less than
.
Output Specification
Output the product .
Sample Input
123456123456123456123456123456123456
987987876876765765654654543543432432321321
Sample Output
121973153300851295215956247283945278187966162014464020099359068031370037005376
Comments
It's possible to
cheesesolve this problem using GMP.This could help : https://www.youtube.com/watch?v=YDhsLhTK3Bs
Any pointers on how to do this in C++ without getting a TLE?
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
I wrote the entire code on my IDE for java only to realize it doesn't allow it..... ;(
Hmmm. Is it possible for you to allow Lua on this question? Or is it not possible?
So close... any tips on improving Karatsuba?
Well Karatsuba was not the intended solution...
Yeah I initially wanted to implement FFT but it didn't quite workout, any idea on how to avoid overflow in NTT, choosing a modulo bigger then
then multiplication overflows but if I choose a modulo smaller then
(for example
) then the result is incorrect (or I can take base
which TLE's).
This comment is hidden due to too much negative feedback. Show it anyway.
Funny thing; I was reading the Java BigInteger documentation, and the fastest multiplication method would take 6 seconds on a worst case.
That is precisely why Java is disallowed.
Couldn't we disable bigInteger and bigDecimal like a + b hard?
There exists a certain
com.sun.media.sound.FFT
, which would trivialize the problem. As we currently do not trivially support the banning of arbitrary packages, Java will continue to be banned.This comment is hidden due to too much negative feedback. Show it anyway.
My Karatsuba pass the tests, even faster than some FFTs implementations.