bansal1232's blog

By bansal1232, history, 7 years ago, In English

What's the right approach of solving this Hackerearth Problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There's an editorial to this problem. If you're still confused after reading it, check Trick #4 here and modification of Sieve of Eratosthenes here.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please Elaborate the 4 trick?

    AN % MOD = AN % phi(MOD) % MOD

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

      This is a natural outcome of Euler's Theorem. If you multiply a number phi(MOD) times modulo MOD you get 1. Suppose N/phi(MOD) = t.

      So A^N % MOD can be written as ((A^phi(MOD))^t)%MOD * (A^(N%phi(MOD)))%MOD. Since the first term is 1 by Euler's Theorem you are left with (A^(N%phi(/MOD)))%MOD.

      Pardon my illiteracy with respect to LATEX.