#6257. 「CodePlus 2017 12 月赛」可做题2

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

“codeplus比赛的时候在做什么?有没有空?能来解决丢番图方程问题吗?”sublinekelzrip这样问qmqmqm。

当然,qmqmqm并不会丢番图方程问题,所以sublinekelzrip改为提出了另一个题目,现在请你帮助qmqmqm解决这个题目。


这个问题是这样的:

若一个数列aaa满足条件an=an−1+an−2,n≥3a_n=a_{n-1}+a_{n-2},n \geq 3an=an1+an2,n3,而a1,a2a_1,a_2a1,a2为任意实数,则我们称这个数列为广义斐波那契数列。

现在请你求出满足条件a1=ia_1=ia1=ia2a_2a2为区间[l,r][l,r][l,r]中的整数,且akmodp=m的广义斐波那契数列有多少个。

输入格式

从标准输入读入数据。

本题包含多组数据,输入第一行包含一个正整数TTT,表示数据组数。对于每组数据:

一行六个用空格隔开的整数i,l,r,k,p,mi,l,r,k,p,mi,l,r,k,p,m,意义如「题目描述」所示。

输出格式

输出到标准输出。

输出共TTT行,每行一个数表示该组数据的答案。

样例

样例输入
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
样例输出
3
1
4
1
5
9

数据范围与提示

测试点kkk rrr 其他
1≤100\leq 100100 ≤100\leq 100100
2≤105\leq 10^5105 ≤105\leq 10^5105
3
4≤1018\leq 10^{18}1018
5
6≤105\leq 10^5105 ≤1018\leq 10^{18}1018 ppp为质数
7
8≤1018\leq 10^{18}1018
9
10

对于所有数据,0≤l≤r0 \leq l \leq r0lr,1≤p≤1091 \leq p \leq 10^91p109,0≤m<p0 \leq m < p0m<p,T=10T=10T=10,0≤i≤10180 \leq i \leq 10^{18}0i1018,k≥3k \geq 3k3


来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/卢政荣 命题/卢政荣 验题/吕时清,茹逸中,王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus201712
感谢腾讯公司对此次比赛的支持。