A Times B

Points: 20 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

FatalEagle

Problem type

Allowed languages

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 $A$ ~A~.

The second line of input will have $B$ ~B~.

Both $A$ ~A~ and $B$ ~B~ will be non-negative integers strictly less than $10^{1\,000\,001}$ ~10^{1\,000\,001}~.

Output Specification

Output the product $A \times B$ ~A \times B~.

Sample Input

123456123456123456123456123456123456
987987876876765765654654543543432432321321

Sample Output

121973153300851295215956247283945278187966162014464020099359068031370037005376

Comments

0

Zafirua 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?
0

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

So close... any tips on improving Karatsuba?

5

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

Well Karatsuba was not the intended solution...

0

kingW3 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 $2^{32}$ ~2^{32}~ then multiplication overflows but if I choose a modulo smaller then $2^{32}$ ~2^{32}~(for example $7\cdot2^{26}+1$ ~7\cdot2^{26}+1~) then the result is incorrect (or I can take base $b=10$ ~b=10~ which TLE's).

-6

dawangk commented on April 16, 2018, 9:07 p.m.

No JAVA?

8

Ninjaclasher commented on April 16, 2018, 10:13 p.m.

read the comment right below you.

V V V V V

-16

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

JAVA unavailable?

Why not JAVA? Isn't BigInteger capable of processing numbers of any range?

4

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

Re: JAVA unavailable?

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

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

Re: JAVA unavailable?

That is precisely why Java is disallowed.

5

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

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

4

Kirito 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.
2

InfernoApeZ commented on Dec. 1, 2017, 3:34 p.m.

yes i agree

7

jkguipqnjcy49979693 commented on Dec. 1, 2017, 9:04 p.m.

I think the reason why it was not allowed later on was because Java is a lot slower than the currently allowed languages; now that custom language limits are allowed, someone needs to write a correct Java solution and then the Time Limits might be set accordingly.

You could always bug Kirito via slack for these things btw, he undoubtedly enjoys it.

As a side note, the current TL is probably too lenient as well because the judges are a lot faster now than they were ~3 yrs ago. (So maybe even Java can pass on the judge with these TLs)

-22

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

Time Limit Changed

Time limit lowered to 2s. Karatsuba shall not pass!

4

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

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