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

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

时间限制:3000 ms 内存限制:128 MB
提交:230 解决:33
[ 提交][ 状态][ 讨论版]

题目描述

在尧老师的指导下，尧老师的孩子学会了五百万以内的加减乘除。为了检验他的学习成果，尧老师找来一根长为1的牙签，k从2开始按顺序每次在k(1

输入

第一行包含一个整数Q(0

输出

每行输出两个整数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，可能是递归爆栈，可以将递归改成非递归写法或者换一种思路。

来源

RedClothes

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