A Times B

View as PDF

Submit solution

Points:30 (partial)
Time limit:2.0s
Memory limit:256M

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.

The second line of input will have B.

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

Output Specification

Output the product A \times B.

Sample Input


Sample Output


Report an issue


  • -15
     commented on Dec. 6, 2015
    JAVA unavailable?

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

    • 1
       commented on June 12, 2016

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

    • 15
       commented on Dec. 6, 2015

      That is precisely why Java is disallowed.

  • -11
     commented on Jan. 15, 2015
    Time Limit Changed

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

    • 0
       commented on Nov. 9, 2017

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