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

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

This comment is hidden due to too much negative feedback. Click here to view it.

This comment is hidden due to too much negative feedback. Click here to view it.

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. Click here to view it.

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.yes i agree

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)

This comment is hidden due to too much negative feedback. Click here to view it.

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