I have a problem about fibonacci numbers: ==================

## let f[i] be the ith fibonacci number

## f[i] = 1 (1 <= i <= 2)

## f[i] = f[i-1] + f[i-2] (i > 2)

how can i calculate f[f[n]] mod M (n, M <= 10^9). anyone can help me?

Before contest

TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)

15:02:37

Register now »

TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)

15:02:37

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 179 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | adamant | 163 |

6 | maroonrk | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | errorgorn | 155 |

I have a problem about fibonacci numbers: ==================

how can i calculate f[f[n]] mod M (n, M <= 10^9). anyone can help me?

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2023 02:32:25 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by hoainiem (previous revision, new revision, compare).https://codeforces.com/blog/entry/18292

i don't think these 2 problems are similar. your problem is calculate the nth fibonacci number , which can be solved by matrix multiplication. but we can't use it to solve my problem because f[n] can be very large, and we can't use modules because (f[f[n]]) mod m is not equal to (f[f[n]mod m] ) mod m

I guess you can try to find pisano period of M, then calculate f[n] mod P(m), where P(i) — pisano period of modulo i, and then calculate the final answer mod M.

Though I'm not sure how to calculate pisano period for such big M, you can try to look for some optimizations here.(also google is your big friend here)

thank you very much. i've tried to google it but i can't find any way to calculate pisano period for m <= 1^9

I (definitely didn't find it in The Ultimate Topic List) found implementation that calculates Pisano period, not sure it'll work with big M, but it might be a good try

i finally get accepted this problem and it's all due to your help. Thanks you.

Glad to hear it :)

Here is the solution https://www.youtube.com/watch?v=dQw4w9WgXcQ

:))

That's a bad way to rickroll people, this tutorial teaches how to do it better.