| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
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.