Блог пользователя azaxnoot

How To Solve ?
Автор azaxnoot, история, 9 лет назад, По-английски

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 .

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить