| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
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 .
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
What is period and how to find it .?? And what is the relation between a, b to period ( as you said ) @vintage_Vlad_Makeev
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.
Actually this is possible to prove that the period is even linear. As I remember it is proven that period is less than 6 * N
There should be something about it.