## A Times B

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Brain****, C, C++, Pascal, Rust

For a while now, FatalEagle has been thinking about fast multiplication. He found the problem on SPOJ, MUL, and solved it without too much trouble. Then he found VFMUL on the same site, but the same code for MUL didn't pass as the SPOJ servers were really slow. Frustrated and desperate to show off demonstrate his fast multiplication code, FatalEagle 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

• commented on Jan. 3, 2023, 2:57 a.m.

It's possible to cheese solve this problem using GMP.

• commented on March 26, 2022, 4:53 a.m.
• commented on Nov. 29, 2021, 2:33 p.m.

Any pointers on how to do this in C++ without getting a TLE?

• commented on Sept. 21, 2019, 2:48 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Jan. 20, 2020, 8:56 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on March 28, 2019, 2:19 a.m.

I wrote the entire code on my IDE for java only to realize it doesn't allow it..... ;(

• commented on Nov. 8, 2018, 6:06 p.m.

Hmmm. Is it possible for you to allow Lua on this question? Or is it not possible?

• commented on Aug. 11, 2018, 4:34 p.m.

So close... any tips on improving Karatsuba?

• commented on Aug. 11, 2018, 5:01 p.m.

Well Karatsuba was not the intended solution...

• commented on Aug. 17, 2018, 2:09 p.m.

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

• commented on Dec. 6, 2015, 9:52 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on June 12, 2016, 10:35 p.m.

Funny thing; I was reading the Java BigInteger documentation, and the fastest multiplication method would take 6 seconds on a worst case.

• commented on Dec. 6, 2015, 9:59 p.m.

That is precisely why Java is disallowed.

• commented on Dec. 1, 2017, 2:39 p.m.

Couldn't we disable bigInteger and bigDecimal like a + b hard?

• commented on Dec. 1, 2017, 10:17 p.m.

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.

• commented on Jan. 15, 2015, 10:15 a.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Nov. 9, 2017, 7:20 a.m.

My Karatsuba pass the tests, even faster than some FFTs implementations.