[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$的广义斐波那契数列有多少个。

输入输出格式

输入格式


从标准输入读入数据。 本题包含多组数据,输入第一行包含一个正整数$T$,表示数据组数。对于每组数据: 一行六个用空格隔开的整数$i,l,r,k,p,m$,意义如「题目描述」所示。

输出格式


输出到标准输出。 输出共$T$行,每行一个数表示该组数据的答案。

输入输出样例

输入样例 #1

6
2 17 68 3 23 1
1 17 68 3 57 1
5 17 68 10 11 9
5 17 68 10 71 9
10 17 68 11 12 3
10 17 68 8 6 4

输出样例 #1

3
1
4
1
5
9

说明

![](https://cdn.luogu.com.cn/upload/pic/12655.png) 对于所有数据,$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 感谢腾讯公司对此次比赛的支持。