问题 1250. -- 尧老师要教孩子数刻度

1250: 尧老师要教孩子数刻度

时间限制: 3 Sec  内存限制: 128 MB
提交: 220  解决: 27
[提交][状态][讨论版]

题目描述

        在尧老师的指导下,尧老师的孩子学会了五百万以内的加减乘除。为了检验他的学习成果,尧老师找来一根长为1的牙签,k从2开始按顺序每次在k(1<k<=m)等分点上划上刻度(若当前位置已有刻度,则不再划)。随后他做出Q个询问,每次给出a,b,c,d,n,m问牙签的a/b处和c/d处之间的第n个刻度是多少。虽然他是尧老师的孩子,但他毕竟刚过满月,有些力不从心,于是他求助于你。

输入

第一行包含一个整数Q(0<Q<=5),表示询问次数。接下来Q行,每行包含6个整数a,b,c,d,n,m(a<=b<10,c<=d<10,a/b<c/d,0<n<=5e6,max(b,d)<=m<=5e6)。牙签的开端以0/1表示,结尾以1/1表示。

输出

每行输出两个整数p,q,表示p/q为查询答案;若a/b点和c/d点之间没有n个刻度,则输出-1.

样例输入

2
0 1 1 1 1 2
0 1 1 1 2 2

样例输出

1 2
-1

提示

样例解释:

第1次操作后,牙签上有1个刻度:1/2

第2次操作后,牙签上有3个刻度:1/3,1/2,2/3

第3次操作后,牙签上有5个刻度:1/4,1/3,1/2,2/3,3/4

而当m=2时,整个牙签上仅有1个刻度(1/2)



提示:

1. 如果毫无思路,建议搜索“法里数列(Farey sequence)”。

2. 如果返回WA,注意a与b的最大公约数或c与d的最大公约数可能大于1。

3. 如果返回RE,可能是递归爆栈,可以将递归改成非递归写法或者换一种思路。

来源

[提交][状态][讨论版]