P4031 [Code+#2] 可做题2

“codeplus比赛的时候在做什么？有没有空？能来解决丢番图方程问题吗？”sublinekelzrip这样问qmqmqm。 当然，qmqmqm并不会丢番图方程问题，所以sublinekelzrip改为提出了另一个题目，现在请你帮助qmqmqm解决这个题目。

这个问题是这样的： 若一个数列$a$满足条件$a_n=a_{n-1}+a_{n-2}$,$n \geq 3$,而$a_1,a_2$为任意实数，则我们称这个数列为广义斐波那契数列。 现在请你求出满足条件$a_1=i$，$a_2$为区间$[l,r]$中的整数，且$a_k mod p = m$的广义斐波那契数列有多少个。

无

无

 对于所有数据，$0 \leq l \leq r$,$1 \leq p \leq 10^9$,$0 \leq m < p$,$T=10$,$0 \leq i \leq 10^{18},k \geq 3$。 来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。 Credit：idea/卢政荣 命题/卢政荣 验题/吕时清，茹逸中，王聿中 Git Repo：https://git.thusaac.org/publish/CodePlus201712 感谢腾讯公司对此次比赛的支持。