deepak_097's blog

Codechef problem — POWOFPOW.

By deepak_097, history, 6 years ago, In English

Please help me to solve this problem.

Problem link- link

Or help me to understand this solution.

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My solution was a bit complicated, the code of the other accepted submission looked really simple, I'm yet to spend time and see what exactly is happening in that solution.

Anyway, I'll explain mine. Remove the corner cases, the solve(base,a,b,n,offset) is trying to return base^((a^b)-offset) % n. First I check if (a^b)==offset by taking log, and then returning 1 if it is, as I don't want to keep increasing offset and go to negative powers. Now, if gcd(base,n)==1. I apply fermat-euler theorem, and I can take ((a^b)-offset) % phi(n), phi is the euler totient function, and then do regular exponentiation. In the other case when they're not coprime, Let's assume gcd(base,n) is g. so I know the answer is definitely going to be a multiple of g. I take it out as common, and I'm left with g * ( g ^ ((a^b)-(offset+1)) * (base/g) ^ ((a^b)-offset) ) % (n/g), which is basically two recursive calls to the same function with modulo reduced by at least 2. Note that (base/g) part will not go any further in recursion, since it now has gcd(base/g,n/g)=1, So effectively the recursion goes ahead one step, dividing the modulo by at least 2. Hence, the recursion goes logn steps in depth, and all other parts are simply exponentiation.

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

    I'm having difficulty in understanding a few things here:

    • Why did the modulus become n/g ? and

    • If gcd(base, n) == g, then why is base mod n, a multiple of g ?

    Maybe the 2nd one is a common question but I didn't find anything comprehensible about this on the internet. Can you please elaborate on the answers to these 2 questions ? It would be helpful.

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

      Let a % b = c, and gcd(a,b) = g.

      You can write a = x*b + c, where b>c && x>=0

      Rearrange it to get a-x*b = c.

      Now I know a%g==0, and b%g==0, so (a-x*b)%g==0. This implies c%g==0.

      Divide the whole equation by g, we get

      (a/g) = x*(b/g) + (c/g)

      This implies (a/g) % (b/g) = (c/g)

      I hope this answers both your questions.

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

        Thanks a lot, the explanation was very helpful. :)

        → Reply