azaxnoot's blog

How To Solve ?
By azaxnoot, history, 9 years ago, In English

Hi , Experts .

Can someone please give me some idea about how to solve this problem . The problem link is in Below .

Link : Problem Link

The modulus Part can be solved by BigMod Operation. But how to calculate a^b here . I have not any idea about how to solve this Part more precisely how to optimize this part . Can someone Help me please .

Thanks in Advance .

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

»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

1 idea: n is very small so f(i) has a small period and we need just (a^b)%some_small_number

2 idea: If a is constant and b is variable, sequence (a^b)%small_number has a small period, so we are just interested it b%another_small_number

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

    What is period and how to find it .?? And what is the relation between a, b to period ( as you said ) @vintage_Vlad_Makeev

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

      The period of f(i) is not more than n2. It's easy to prove it:

      f(i)=(f(i — 1)%n + f(i — 2)%n)%n. But there are only n possible values of f(i — 1)%n, so there are only n2 possible values of (f(i — 1)%n + f(i — 2)%n)%n. That shows that after not more than n2 steps we will get into cycle. You can find easily. If you have already seen this f(i — 1)%n + f(i — 2)%n then all pairs between current position and last occurence of this pair is cycle.

      (a^b)%p has a cycle of length not more than p, because each value depends only on previous and we have p possible values.

      → Reply