Not-Afraid's blog

Help in Self Powers(Project Euler Hackerrank problem 48)
By Not-Afraid, history, 5 years ago, In English

I am getting TLE on last test case of this problem Link to the problem, i used Big mod Link to Big mod implmentation for multiplication while calculating power as we need last ten digits so we have to modulo it by 1e10 which will overflow in C++.

Any type of help is appreciated. Thanks in advance.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Not-Afraid (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

BigMod implementation adds another factor of $$$log (MOD)$$$, making the time complexity $$$O(n log n log MOD)$$$.To remove the $$$log (MOD)$$$ factor, You can compute the remainder modulo $$$2^{10}$$$ and $$$5^{10}$$$, and then find the remainder modulo $$$10^{10}$$$ using chinese remainder theorem.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can we do it without CRT ??

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks! I solved it using CRT. Solution

    I found an implementation for Big mod in Discussion form of this question Ideone Link but couldn't understand what is it doing exactly, if you can help?

    → Reply