How to calculate the fibonacci entry point for N numbers p1, p2, p3, ...., pn. (1 < = pi < = 109)
FEP(pi) = j such that jth fibonacci number is the first fibonacci number Fj divisible by pi
How can we find it efficiently for N numbers.
Ex,
input = 2, output = 3
input = 5, output = 5
input = 13, output = 7
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
If p is prime, the answer is divisor of p + 1 (except when p = 5). So check all p + 1 divisors with fast matrix power algorithm.
If p = 11, answer is 10. 10 is not divisor of 12. And what if p is not prime.
Looks like it could be divisor of p − 1 too. Could be dependent on whether square root of 5 exists (that's why p = 5 is an exception) which is true if and only if p = 5n ± 1. For non-prime modulos you will need to combine answers with lcm for several powers of primes. To calculate the answer for the power of prime, you will need to check whether you need to multiply by p the answer for smaller power of prime.